第1章 緒論 1
1.1 為什麼要學習算法 1
1.2 整數乘法 3
1.2.1 問題和解決方案 3
1.2.2 整數乘法問題 3
1.2.3 小學算法 4
1.2.4 操作數量的分析 5
1.2.5 還能做得更好嗎 5
1.3 Karatsuba乘法 6
1.3.1 一個具體的例子 6
1.3.2 一種遞歸算法 7
1.3.3 Karatsuba乘法 9
1.4 MergeSort算法 11
1.4.1 推動力 11
1.4.2 排序 12
1.4.3 一個例子 13
1.4.4 僞碼 14
1.4.5 Merge子程序 15
1.5 MergeSort算法分析 16
1.5.1 Merge的運行時間 17
1.5.2 MergeSort的運行時間 18
1.5.3 定理1.2的證明 19
1.5.4 小測驗1.1～1.2的答案 23
1.6 算法分析的指導原則 23
1.6.1 第1個原則：最壞情況分析 24
1.6.2 第2個原則：全局分析 25
1.6.3 第3個原則：漸進性分析 26
1.6.4 什麼是“快速”算法 27
1.7 本章要點 28
1.8 習題 29
挑戰題 31
編程題 31
第2章 漸進性錶示法 32
2.1 要旨 32
2.1.1 推動力 32
2.1.2 高級思維 33
2.1.3 4個例子 34
2.1.4 小測驗2.1～2.4的答案 38
2.2 大O錶示法 40
2.2.1 文本定義 40
2.2.2 圖形定義 40
2.2.3 數學定義 41
2.3 兩個基本例子 42
2.3.1 k階多項式是O(nk) 42
2.3.2 k階多項式不是O(nk-1) 43
2.4 大Ω和大錶示法 44
2.4.1 大Ω錶示法 44
2.4.2 大錶示法 45
2.4.3 小O錶示法 46
2.4.4 漸進性錶示法的來源 47
2.4.5 小測驗2.5的答案 48
2.5 其他例子 48
2.5.1 在指數中添加一個常數 48
2.5.2 指數乘以一個常數 49
2.5.3 最大值vs.和 49
2.6 本章要點 50
2.7 習題 51
第3章 分治算法 53
3.1 分治法規範 53
3.2 以O(n log n)時間計數逆序對 54
3.2.1 問題 54
3.2.2 一個例子 54
3.2.3 協同篩選 55
3.2.4 窮舉搜索法 55
3.2.5 分治法 56
3.2.6 高級算法 57
3.2.7 關鍵思路：站在MergeSort的肩膀上 57
3.2.8 重溫Merge 58
3.2.9 Merge和分離逆序對 60
3.2.10 Merge_and_CountSplitInv 61
3.2.11 正確性 61
3.2.12 運行時間 62
3.2.13 小測驗3.1～3.2的答案 62
3.3 Strassen的矩陣相乘算法 63
3.3.1 矩陣相乘 63
3.3.2 例子（n = 2） 64
3.3.3 簡單算法 64
3.3.4 分治法 65
3.3.5 節省一個遞歸調用 67
3.3.6 細節 68
3.3.7 小測驗3.3的答案 69
*3.4 O(n log n)時間的最近點對（Closest Pair）算法 70
3.4.1 問題 70
3.4.2 熱身：1D情況 71
3.4.3 預處理 71
3.4.4 一種分治方法 72
3.4.5 一個微妙的變化 74
3.4.6 ClosestSplitPair 74
3.4.7 正確性 76
3.4.8 輔助結論3.3（a）的證明 77
3.4.9 輔助結論3.3（b）的證明 78
3.4.10 小測驗3.4的答案 80
3.5 本章要點 80
3.6 習題 81
挑戰題 81
編程題 82
第4章 主方法 83
4.1 重溫整數乘法 83
4.1.1 RecIntMult算法 84
4.1.2 Karatsuba算法 84
4.1.3 比較遞歸過程 85
4.2 形式聲明 86
4.2.1 標準遞歸過程 86
4.2.2 主方法的陳述和討論 87
4.3 6個例子 88
4.3.1 重溫MergeSort 89
4.3.2 二分搜索 89
4.3.3 整數乘法的遞歸算法 90
4.3.4 Karatsuba乘法 90
4.3.5 矩陣乘法 91
4.3.6 一個虛構的遞歸過程 92
4.3.7 小測驗4.2～4.3的答案 93
*4.4 主方法的證明 94
4.4.1 前言 94
4.4.2 重溫遞歸樹 95
4.4.3 單層所完成的工作 96
4.4.4 各層纍計 97
4.4.5 正義與邪惡：需要考慮3種情況 98
4.4.6 預告運行時間上界 99
4.4.7 最後的計算：第一種情況 100
4.4.8 迂迴之旅：幾何級數 101
4.4.9 最後的計算：第二種情況和第三種情況 102
4.4.10 小測驗4.4～4.5的答案 103
4.5 本章要點 103
4.6 習題 104
第5章 快速排序（QuickSort） 107
5.1 概述 107
5.1.1 排序 108
5.1.2 根據基準元素進行劃分 108
5.1.3 高級描述 110
5.1.4 內容前瞻 110
5.2 圍繞基準元素進行劃分 111
5.2.1 簡易方法 111
5.2.2 原地實現：高級計劃 112
5.2.3 例子 113
5.2.4 Partition子程序的僞碼 115
5.2.5 QuickSort的僞碼 117
5.3 良好的基準元素的重要性 117
5.3.1 ChoosePivot的簡單實現 118
5.3.2 ChoosePivot的過度實現 118
5.3.3 小測驗5.1～5.2的答案 119
5.4 隨機化的QuickSort 121
5.4.1 ChoosePivot的隨機化實現 121
5.4.2 隨機化QuickSort的運行時間 122
5.4.3 直覺：隨機基準元素為什麼很好 123
*5.5 隨機化QuickSort的分析 124
5.5.1 預備工作 125
5.5.2 分解藍圖 126
5.5.3 應用藍圖 128
5.5.4 計算比較的概率 130
5.5.5 最後的計算 132
5.5.6 小測驗5.3的答案 133
*5.6 排序需要 (n log n)的比較 134
5.6.1 基於比較的排序算法 134
5.6.2 具有更強前提的更快速排序 135
5.6.3 定理5.5的證明 136
5.7 本章要點 138
5.8 習題 139
挑戰題 140
編程題 141
第6章 綫性時間級的選擇 142
6.1 RSelect算法 143
6.1.1 選擇問題 143
6.1.2 簡化為排序 144
6.1.3 分治法 145
6.1.4 RSelect的僞碼 146
6.1.5 RSelect的運行時間 147
6.1.6 小測驗6.1～6.2的答案 149
*6.2 RSelect的分析 150
6.2.1 根據階段追蹤進展 150
6.2.2 簡化為擲硬幣 151
6.2.3 綜閤結論 153
*6.3 DSelect算法 154
6.3.1 基本思路：中位的中位元素 154
6.3.2 DSelect的僞碼 155
6.3.3 理解DSelect 156
6.3.4 DSelect的運行時間 157
*6.4 DSelect的分析 159
6.4.1 遞歸調用之外所完成的工作 159
6.4.2 一個粗略的遞歸過程 159
6.4.3 30-70輔助結論 160
6.4.4 解析遞歸過程 163
6.4.5 先猜後驗方法 164
6.5 本章要點 166
6.6 本章習題 166
挑戰題 167
編程題 168
附錄A 快速迴顧數學歸納法 169
附錄B 快速迴顧離散概率 173
· · · · · · (收起)
1.1 為什麼要學習算法 1
1.2 整數乘法 3
1.2.1 問題和解決方案 3
1.2.2 整數乘法問題 3
1.2.3 小學算法 4
1.2.4 操作數量的分析 5
1.2.5 還能做得更好嗎 5
1.3 Karatsuba乘法 6
1.3.1 一個具體的例子 6
1.3.2 一種遞歸算法 7
1.3.3 Karatsuba乘法 9
1.4 MergeSort算法 11
1.4.1 推動力 11
1.4.2 排序 12
1.4.3 一個例子 13
1.4.4 僞碼 14
1.4.5 Merge子程序 15
1.5 MergeSort算法分析 16
1.5.1 Merge的運行時間 17
1.5.2 MergeSort的運行時間 18
1.5.3 定理1.2的證明 19
1.5.4 小測驗1.1～1.2的答案 23
1.6 算法分析的指導原則 23
1.6.1 第1個原則：最壞情況分析 24
1.6.2 第2個原則：全局分析 25
1.6.3 第3個原則：漸進性分析 26
1.6.4 什麼是“快速”算法 27
1.7 本章要點 28
1.8 習題 29
挑戰題 31
編程題 31
第2章 漸進性錶示法 32
2.1 要旨 32
2.1.1 推動力 32
2.1.2 高級思維 33
2.1.3 4個例子 34
2.1.4 小測驗2.1～2.4的答案 38
2.2 大O錶示法 40
2.2.1 文本定義 40
2.2.2 圖形定義 40
2.2.3 數學定義 41
2.3 兩個基本例子 42
2.3.1 k階多項式是O(nk) 42
2.3.2 k階多項式不是O(nk-1) 43
2.4 大Ω和大錶示法 44
2.4.1 大Ω錶示法 44
2.4.2 大錶示法 45
2.4.3 小O錶示法 46
2.4.4 漸進性錶示法的來源 47
2.4.5 小測驗2.5的答案 48
2.5 其他例子 48
2.5.1 在指數中添加一個常數 48
2.5.2 指數乘以一個常數 49
2.5.3 最大值vs.和 49
2.6 本章要點 50
2.7 習題 51
第3章 分治算法 53
3.1 分治法規範 53
3.2 以O(n log n)時間計數逆序對 54
3.2.1 問題 54
3.2.2 一個例子 54
3.2.3 協同篩選 55
3.2.4 窮舉搜索法 55
3.2.5 分治法 56
3.2.6 高級算法 57
3.2.7 關鍵思路：站在MergeSort的肩膀上 57
3.2.8 重溫Merge 58
3.2.9 Merge和分離逆序對 60
3.2.10 Merge_and_CountSplitInv 61
3.2.11 正確性 61
3.2.12 運行時間 62
3.2.13 小測驗3.1～3.2的答案 62
3.3 Strassen的矩陣相乘算法 63
3.3.1 矩陣相乘 63
3.3.2 例子（n = 2） 64
3.3.3 簡單算法 64
3.3.4 分治法 65
3.3.5 節省一個遞歸調用 67
3.3.6 細節 68
3.3.7 小測驗3.3的答案 69
*3.4 O(n log n)時間的最近點對（Closest Pair）算法 70
3.4.1 問題 70
3.4.2 熱身：1D情況 71
3.4.3 預處理 71
3.4.4 一種分治方法 72
3.4.5 一個微妙的變化 74
3.4.6 ClosestSplitPair 74
3.4.7 正確性 76
3.4.8 輔助結論3.3（a）的證明 77
3.4.9 輔助結論3.3（b）的證明 78
3.4.10 小測驗3.4的答案 80
3.5 本章要點 80
3.6 習題 81
挑戰題 81
編程題 82
第4章 主方法 83
4.1 重溫整數乘法 83
4.1.1 RecIntMult算法 84
4.1.2 Karatsuba算法 84
4.1.3 比較遞歸過程 85
4.2 形式聲明 86
4.2.1 標準遞歸過程 86
4.2.2 主方法的陳述和討論 87
4.3 6個例子 88
4.3.1 重溫MergeSort 89
4.3.2 二分搜索 89
4.3.3 整數乘法的遞歸算法 90
4.3.4 Karatsuba乘法 90
4.3.5 矩陣乘法 91
4.3.6 一個虛構的遞歸過程 92
4.3.7 小測驗4.2～4.3的答案 93
*4.4 主方法的證明 94
4.4.1 前言 94
4.4.2 重溫遞歸樹 95
4.4.3 單層所完成的工作 96
4.4.4 各層纍計 97
4.4.5 正義與邪惡：需要考慮3種情況 98
4.4.6 預告運行時間上界 99
4.4.7 最後的計算：第一種情況 100
4.4.8 迂迴之旅：幾何級數 101
4.4.9 最後的計算：第二種情況和第三種情況 102
4.4.10 小測驗4.4～4.5的答案 103
4.5 本章要點 103
4.6 習題 104
第5章 快速排序（QuickSort） 107
5.1 概述 107
5.1.1 排序 108
5.1.2 根據基準元素進行劃分 108
5.1.3 高級描述 110
5.1.4 內容前瞻 110
5.2 圍繞基準元素進行劃分 111
5.2.1 簡易方法 111
5.2.2 原地實現：高級計劃 112
5.2.3 例子 113
5.2.4 Partition子程序的僞碼 115
5.2.5 QuickSort的僞碼 117
5.3 良好的基準元素的重要性 117
5.3.1 ChoosePivot的簡單實現 118
5.3.2 ChoosePivot的過度實現 118
5.3.3 小測驗5.1～5.2的答案 119
5.4 隨機化的QuickSort 121
5.4.1 ChoosePivot的隨機化實現 121
5.4.2 隨機化QuickSort的運行時間 122
5.4.3 直覺：隨機基準元素為什麼很好 123
*5.5 隨機化QuickSort的分析 124
5.5.1 預備工作 125
5.5.2 分解藍圖 126
5.5.3 應用藍圖 128
5.5.4 計算比較的概率 130
5.5.5 最後的計算 132
5.5.6 小測驗5.3的答案 133
*5.6 排序需要 (n log n)的比較 134
5.6.1 基於比較的排序算法 134
5.6.2 具有更強前提的更快速排序 135
5.6.3 定理5.5的證明 136
5.7 本章要點 138
5.8 習題 139
挑戰題 140
編程題 141
第6章 綫性時間級的選擇 142
6.1 RSelect算法 143
6.1.1 選擇問題 143
6.1.2 簡化為排序 144
6.1.3 分治法 145
6.1.4 RSelect的僞碼 146
6.1.5 RSelect的運行時間 147
6.1.6 小測驗6.1～6.2的答案 149
*6.2 RSelect的分析 150
6.2.1 根據階段追蹤進展 150
6.2.2 簡化為擲硬幣 151
6.2.3 綜閤結論 153
*6.3 DSelect算法 154
6.3.1 基本思路：中位的中位元素 154
6.3.2 DSelect的僞碼 155
6.3.3 理解DSelect 156
6.3.4 DSelect的運行時間 157
*6.4 DSelect的分析 159
6.4.1 遞歸調用之外所完成的工作 159
6.4.2 一個粗略的遞歸過程 159
6.4.3 30-70輔助結論 160
6.4.4 解析遞歸過程 163
6.4.5 先猜後驗方法 164
6.5 本章要點 166
6.6 本章習題 166
挑戰題 167
編程題 168
附錄A 快速迴顧數學歸納法 169
附錄B 快速迴顧離散概率 173
· · · · · · (收起)
具體描述
算法是計算機科學領域最重要的基石之一。算法是程序的靈魂，隻有掌握瞭算法，纔能輕鬆地駕馭程序開發。
算法詳解係列圖書共有4捲，本書是第1捲——算法基礎。本書共有6章，主要介紹瞭4個主題，它們分彆是漸進性分析和大O錶示法、分治算法和主方法、隨機化算法以及排序和選擇。附錄A和附錄B簡單介紹瞭數據歸納法和離散概率的相關知識。本書的每一章均有小測驗、章末習題和編程題，這為讀者的自我檢查以及進一步學習提供瞭較多的便利。
本書為對算法感興趣的廣大讀者提供瞭豐富而實用的資料，能夠幫助讀者提升算法思維能力。本書適閤計算機專業的高校教師和學生，想要培養和訓練算法思維和計算思維的IT專業人士，以及在準備麵試的應聘者和麵試官閱讀參考。
用戶評價
評分
##這本書雖然比較薄，但是專注於一個分治算法主題來講，從基本原則到經典應用算法排序，再到最後的選擇問題；中途算法分析和證明，有比較深入的分析
評分
##一整本書（雖然特彆薄）都在講分治。讓遞歸服服帖帖的。
評分
##精讀過，講解行雲流水乾脆利落，對於入門確實是上層好書，在豆瓣和當當會看到一些無知無謂的評論左右著評分，這些讀者應該沒有仔細閱讀和研究過，書有少量翻譯以及印刷上的錯誤，但不影響閱讀判斷，有時間再寫書評。
評分
看視頻學算法，so easy!
評分
##精讀過，講解行雲流水乾脆利落，對於入門確實是上層好書，在豆瓣和當當會看到一些無知無謂的評論左右著評分，這些讀者應該沒有仔細閱讀和研究過，書有少量翻譯以及印刷上的錯誤，但不影響閱讀判斷，有時間再寫書評。
評分
##逆序數，點對距離，題目選的不錯，不過看瞭下Kleinberg分治那一章，原來似曾相識啊
評分
看視頻學算法，so easy!
評分
##一整本書（雖然特彆薄）都在講分治。讓遞歸服服帖帖的。
##輕鬆愉快，適閤復習（總算看懂主定理的證明瞭