算法之道

前言
第一篇 算法基礎篇
第1章 從無有到無窮 2
1.1 意念與現(xiàn)實 3
1.2 什么是算法 4
1.3 算法的表示 6
1.4 算法之魂 7
1.5 如何比較速度 8
1.6 算法與計算機的關系 9
1.7 算法的范疇 10
1.8 為什么學習算法 10
思考題 11
第2章 計數(shù)與漸近 12
2.1 算法的分析 12
2.1.1 正確性分析 13
2.1.2 時空效率分析 14
2.1.3 時空特性分析 14
2.2 計數(shù)：算法分析的核心 14
2.3 算法設計 15
2.4 算法效率表示 16
2.5 漸近分析 17
2.6 O表示 18
2.7 最好、最壞、平均 19
2.8 O的另一類定義 21
2.9 O的性質 22
2.10 要更快的計算機還是要更快的算法 22
思考題 23
第3章 分治與遞歸 25
3.1 分而治之為上策 26
3.2 分治策略 28
3.3 遞歸表達式求解 29
3.3.1 遞歸樹法 29
3.3.2 替換解法 30
3.3.3 大師解法 32
3.4 分治策略舉例1：乘方運算 35
3.5 生命不能承受之重：矩陣乘法 36
3.6 魔鬼序列：斐波那契序列 38
3.7 VLSI 布線 41
3.8 多項式乘法 43
3.9 分治就在潛意識深處 43
思考題 43
第二篇 算法設計篇
第4章 動態(tài)規(guī)劃思想 46
4.1 什么是動態(tài)規(guī)劃 47
4.2 流水裝配線問題 48
4.3 最長公共子序列 52
4.3.1 第一種解法：蠻力策略 52
4.3.2 第二種解法：動態(tài)規(guī)劃 53
4.4 最長公共子序列變種 55
4.5 記憶遞歸法 55
4.6 空間效率改善 56
4.7 最優(yōu)二叉搜索樹 56
4.7.1 遞歸解法 59
4.7.2 計算最優(yōu)答案 59
4.8 最優(yōu)子結構與重疊子問題 62
4.8.1 最優(yōu)子結構 62
4.8.2 重疊子問題 63
4.9 動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關系 63
4.10 動態(tài)規(guī)劃與靜態(tài)規(guī)劃的相互轉換 64
思考題 65
第5章 貪婪選擇思想 67
5.1 僅有動態(tài)規(guī)劃是不夠的 67
5.2 什么是貪婪 68
5.3 背包問題 68
5.4 貪婪選擇屬性 71
5.5 教室規(guī)劃問題 72
5.6 最小生成樹 76
5.6.1 Kruskal算法的正確性 79
5.6.2 Kruskal算法的時間分析 80
5.7 Prim算法 80
5.8 霍夫曼樹和霍夫曼編碼 83
5.8.1 霍夫曼樹 85
5.8.2 霍夫曼編碼 86
5.8.3 霍夫曼編碼的無前綴編碼性質 87
5.9 貪婪選擇屬性 88
5.10 標準分治、動態(tài)規(guī)劃和貪婪選擇的比較 89
思考題 90
第6章 隨機化思想 92
6.1 為什么要隨機化 93
6.2 隨機的平方 94
6.3 什么是隨機化算法 95
6.4 拉斯維加斯算法 96
6.5 蒙特卡羅算法 97
6.6 素性測試 97
6.7 矩陣乘積驗證器 100
6.8 隨機化最小生成樹算法 102
6.8.1 Karger-Klein-Tarjan算法 103
6.8.2 節(jié)點降低算法 103
6.8.3 線性時間最小生成樹算法 104
6.8.4 線性時間最小生成樹算法的時間成本分析 104
6.9 隨機數(shù)的生成 105
6.10 隨機化算法的應用 105
思考題 106
第三篇 算法分析篇
第7章 概率分析 108
7.1 一切都在概率中 109
7.2 什么是概率分析 109
7.3 夢幻情人的代價 110
7.3.1 直接分析 112
7.3.2 最壞情況分析 113
7.3.3 最好情況分析 113
7.3.4 平均情況分析 113
7.3.5 平均情況下成本的概率分析 113
7.4 概率分析結果的有效性 114
7.5 正確概率分析的保障 115
7.6 夢幻情人的概率 115
7.7 隨機排列問題 117
7.8 南柯一夢：從無窮到無有 119
7.9 概率分析的其他應用 120
思考題 121
第8章 攤銷分析 122
8.1 什么是攤銷分析 123
8.2 攤銷分析與數(shù)據(jù)結構 124
8.3 攤銷分析的幾種方法 124
8.4 聚類分析 125
8.4.1 棧操作的聚類分析 125
8.4.2 二進制計數(shù)器的聚類分析 126
8.5 會計分析 128
8.6 勢能分析 130
8.6.1 棧操作的勢能分析 130
8.6.2 二進制計數(shù)器的勢能分析 131
8.7 攤銷分析應用：表格擴展的代價 131
8.7.1 動態(tài)表插入操作的聚類分析 134
8.7.2 動態(tài)表插入操作的會計分析 134
8.7.3 動態(tài)表插入操作的勢能分析 136
8.8 運氣不好就攤銷 137
思考題 138
第9章 競爭分析 139
9.1 什么是競爭分析 139
9.2 在線算法和離線算法 141
9.3 競爭力 142
9.4 健忘對手和優(yōu)良對手 142
9.5 線性表更新問題 143
9.6 前置移動算法的競爭分析 145
9.7 聚類問題 147
9.7.1 聚類問題的次優(yōu)解算法 148
9.7.2 CLUSTERING-ALGORITHM算法的競爭分析 148
9.8 競爭分析與普通算法分析 149
思考題 149
第四篇 經(jīng)典算法篇
第10章 排序和次序 152
10.1 排序無處不在 152
10.2 插入排序 153
10.2.1 插入排序的效率分析 154
10.2.2 折半插入排序 155
10.3 歸并排序 156
10.4 快速排序 158
10.4.1 快速排序的過程 158
10.4.2 快速排序的時間復雜性分析 159
10.4.3 最壞情況分析 160
10.4.4 最好情況分析 160
10.4.5 平均情況分析 161
10.5 隨機化快速排序 162
10.6 排序的下限 164
10.7 線性排序 165
10.8 計數(shù)排序 166
10.9 基數(shù)排序 168
10.9.1 基數(shù)排序的正確性 169
10.9.2 基數(shù)排序的時間效率分析 170
10.10 桶排序 171
10.10.1 桶排序的定義 172
10.10.2 桶排序的正確性 173
10.10.3 桶排序的時間復雜性分析 173
10.11 次序選擇 175
10.12 快速次序選擇算法 176
10.13 隨機快速次序選擇算法 178
10.14 最壞情況下的線性選擇算法 179
10.14.1 杠桿點好壞分析 180
10.14.2 算法的時間復雜性分析 181
思考題 181
第11章 搜索與哈希 183
11.1 搜索問題 184
11.2 順序搜索 184
11.3 折半搜索 185
11.4 常數(shù)搜索 186
11.5 哈希搜索 187
11.6 哈希函數(shù)選擇 189
11.6.1 直接哈希 189
11.6.2 除法（模除法）哈希 190
11.6.3 乘法哈希 191
11.6.4 乘法哈希的賭徒原理 192
11.6.5 乘方取中法 193
11.7 哈希算法的碰撞問題 193
11.7.1 開放尋址哈希 193
11.7.2 開放尋址哈希的時間成本 194
11.7.3 開放尋址下成功搜索的時間成本 195
11.7.4 封閉尋址哈希 196
11.7.5 探尋序列的設計 197
11.7.6 封閉尋址哈希的效率分析 199
11.7.7 搜索不成功的時間成本 199
11.7.8 成功搜索的效率分析 201
11.8 哈希表元素刪除 201
11.9 隨機化哈希 202
11.10 全域哈希 203
11.11 全域哈希構造 204
11.12 完美哈希 206
思考題 208
第12章 最短路徑 211
12.1 劍指羅馬 211
12.2 最短路徑問題 213
12.3 單源單點最短路徑問題 215
12.3.1 深度優(yōu)先搜索與廣度優(yōu)先搜索 215
12.3.2 深度優(yōu)先解法 217
12.4 單源多點最短路徑問題 218
12.4.1 最短路徑的性質 219
12.4.2 Dijkstra最短路徑算法 220
12.4.3 Dijkstra算法舉例 221
12.4.4 Dijkstra算法與洪水泛濫 222
12.4.5 Dijkstra算法的正確性 223
12.4.6 Dijkstra算法的時間復雜性 224
12.5 Bellman-Ford算法 226
12.5.1 負權重的應對方式 227
12.5.2 Bellman-Ford算法的正確性 230
12.5.3 負循環(huán)檢查問題 231
12.5.4 Bellman-Ford算法的時間復雜性 231
12.6 多源多點最短路徑問題 232
12.6.1 多源多點最短路徑問題解決思路 232
12.6.2 直接動態(tài)規(guī)劃解法 233
12.6.3 矩陣乘法解法 234
12.6.4 Floyd-Warshall 算法 235
12.6.5 Johnson 算法 236
12.6.6 Johnson等效變換 237
12.6.7 差限問題解決 238
12.7 天意難違 240
思考題 240
第五篇 難解與無解篇
第13章 可解與不可解 244
13.1 我們戰(zhàn)無不勝嗎 245
13.2 易解與難解 245
13.3 決策問題和優(yōu)化問題 246
13.4 決策問題 247
13.5 P類問題 247
13.6 NP類問題 248
13.7 （確定性）圖靈機 249
13.8 非確定性圖靈機 249
13.9 非確定性算法 250
13.10 回到NP類問題 251
13.11 P和NP 252
13.12 搜索問題、決策問題和優(yōu)化問題 253
13.13 有沒有解和是否可決定 253
思考題 254
第14章 NP完全問題 256
14.1 玉龍雪山下的審判 256
14.2 NP完全問題的定義 257
14.3 NP完全的重要性 258
14.4 多項式時間規(guī)約 259
14.5 如何證明一個問題S是NP完全 259
14.6 第1個NP完全問題的證明 260
14.7 庫克定理 260
14.8 3-SAT問題 263
14.9 證明NP難的技巧 264
14.10 整數(shù)規(guī)劃 265
14.11 獨立集問題 266
14.12 漢密爾頓回路問題 268
14.13 討論：弱NP完全、強NP完全和中NP完全 271
思考題 272
第15章 無解與近似 273
15.1 難解問題 274
15.2 不可決定問題 274
15.3 程序終結的判斷 275
15.4 難解之題的求解 276
15.5 智能窮舉、近似算法和本地搜索 277
15.6 智能窮舉之回溯策略 279
15.7 智能窮舉之分支限界 280
15.8 貪婪近似策略 280
15.9 啟發(fā)式搜索策略 281
15.10 模擬淬火算法 282
15.10.1 模擬淬火算法的思想 284
15.10.2 模擬淬火算法的基本循環(huán) 284
15.10.3 淬火算法描述 284
思考題 286
結語 算法之道 288
附錄 算法隨想 290
參考文獻 293