前言
第一篇 算法基礎篇
第1章 從無有到無窮 3
1.1 意念與現實 4
1.2 什麼是算法 5
1.3 算法的錶示 7
1.4 算法之魂 8
1.5 如何比較速度 9
1.6 算法與計算機的關係 10
1.7 算法的範疇 11
1.8 為什麼學習算法 11
思考題 12
第2章 計數與漸近 13
2.1 算法的分析 13
2.1.1 正確性分析 14
2.1.2 時空效率分析 15
2.1.3 時空特性分析 15
2.2 計數：算法分析的核心 15
2.3 算法設計 16
2.4 算法效率錶示 17
2.5 漸近分析 18
2.6 O、?、(錶示 19
2.7 最好、最壞、平均 20
2.8 O、?、(的另一類定義 22
2.9 O、?、( 的性質 23
2.10 要更快的計算機還是要更快的算法 23
思考題 24
第3章 分治與遞歸 27
3.1 分而治之為上策 28
3.2 分治策略 30
3.3 遞歸錶達式求解 31
3.3.1 遞歸樹法 31
3.3.2 替換解法 32
3.3.3 大師解法 34
3.4 分治策略舉例1：乘方運算 37
3.5 生命中不能承受之重：矩陣乘法 37
3.6 魔鬼序列：斐波那契序列 40
3.6.1 由底至上 42
3.6.2 使用通式 42
3.6.3 使用矩陣乘方 42
3.7 VLSI 布綫 43
3.8 多項式乘法 44
3.9 分治就在潛意識 44
思考題 45
第二篇 算法設計篇
第4章 動態規劃思想 49
4.1 什麼是動態規劃 51
4.2 流水綫問題 51
4.3 最長公共子序列 55
4.3.1 第一種解法：蠻力策略 56
4.3.2 第二種解法：動態規劃 57
4.4 最長公共子序列變種 59
4.5 記憶遞歸法 59
4.6 空間效率改善 60
4.7 最優二叉搜索樹 60
4.7.1 遞歸解法 63
4.7.2 計算最優答案 64
4.8 最優子結構與重疊子問題 66
4.8.1 最優子結構 67
4.8.2 重疊子問題 67
4.9 動態規劃與靜態規劃的關係 68
4.10 動態規劃與靜態規劃的相互轉換 69
思考題 69
第5章 貪婪選擇思想 71
5.1 僅有動態規劃是不夠的 71
5.2 什麼是貪婪 72
5.3 背包問題 72
5.4 貪婪選擇屬性 75
5.5 教室規劃問題 75
5.6 最小生成樹 79
5.6.1 Kruskal算法的正確性 83
5.6.2 Kruskal算法的時間分析 83
5.7 Prim算法 84
5.8 霍夫曼樹和霍夫曼編碼 87
5.8.1 霍夫曼樹 89
5.8.2 霍夫曼編碼 90
5.8.3 霍夫曼編碼的無前綴編碼性質 91
5.9 進程調度問題 92
5.10 貪婪選擇屬性 92
5.11 標準分治、動態規劃和貪婪選擇的比較 94
思考題 95
第6章 隨機化思想 97
6.1 為什麼要隨機化 98
6.2 隨機的平方 99
6.3 什麼是隨機化算法 100
6.4 拉斯維加斯算法 101
6.5 濛特卡羅算法 102
6.6 素性測試 103
6.7 矩陣乘積驗證器 105
6.8 隨機化最小生成樹算法 107
6.8.1 Karger-Klein-Tarjan算法 108
6.8.2 結點降低算法 109
6.8.3 綫性時間最小生成樹算法 109
6.8.4 綫性時間最小生成樹算法的時間成本分析 109
6.9 隨機數的生成 110
6.10 隨機化算法的應用 111
思考題 111
第三篇 算法分析篇
第7章 概率分析 115
7.1 一切都在概率中 116
7.2 什麼是概率分析 117
7.3 夢幻情人的代價 117
7.3.1 直接分析 119
7.3.2 最壞情況分析 119
7.3.3 最好情況分析 120
7.3.4 平均情況分析 120
7.3.5 平均情況下成本的概率分析 120
7.3.6 概率分析結果的有效性 121
7.3.7 正確概率分析的保障 122
7.4 夢幻情人的概率 122
7.5 隨機排列問題 124
7.6 跳轉錶問題 126
7.6.1 跳轉錶插入操作 128
7.6.2 隨機化跳轉錶構建算法 128
7.7 南柯一夢：從無窮到無有 130
7.8 概率分析的其他應用 132
思考題 132
第8章 攤銷分析 135
8.1 什麼是攤銷分析 136
8.2 攤銷分析與數據結構 137
8.3 攤銷分析的幾種方法 138
8.4 聚類分析 138
8.4.1 棧操作的聚類分析 139
8.4.2 二進製計數器的聚類分析 140
8.5 會計分析 141
8.6 勢能分析 143
8.6.1 棧操作的勢能分析 144
8.6.2 二進製計數器的勢能分析 144
8.7 攤銷分析應用：錶格擴展的代價 145
8.7.1 動態錶插入操作的聚類分析 147
8.7.2 動態錶插入操作的會計分析 148
8.7.3 動態錶插入操作的勢能分析 149
8.8 運氣不好就攤銷 150
思考題 151
第9章 競爭分析 153
9.1 什麼是競爭分析 153
9.2 在綫算法和離綫算法 154
9.3 競爭力 156
9.4 健忘對手和優良對手 156
9.5 綫性錶更新問題 157
9.6 前置移動算法的競爭分析 159
9.7 聚類問題 161
9.7.1 聚類問題的次優解算法 162
9.7.2 CLUSTERING-ALGORITHM算法的競爭分析 162
9.8 競爭分析與普通算法分析 163
思考題 163
第四篇 經典算法篇
第10章 排序與次序 169
10.1 排序無處不在 169
10.2 插入排序 170
10.2.1 插入排序的效率分析 172
10.2.2 摺半插入排序 172
10.3 歸並排序 173
10.4 快速排序 175
10.4.1 快速排序的過程 175
10.4.2 快速排序的時間復雜性分析 177
10.4.3 最壞情況分析 177
10.4.4 最好情況分析 177
10.4.5 平均情況分析 178
10.5 隨機化快速排序 179
10.6 排序的下限 181
10.7 綫性排序 182
10.8 計數排序 183
10.9 基數排序 186
10.9.1 基數排序的正確性 187
10.9.2 基數排序的時間效率分析 187
10.10 桶排序 189
10.10.1 桶排序的定義 190
10.10.2 桶排序的正確性 190
10.10.3 桶排序的時間復雜性分析 191
10.11 次序選擇 192
10.12 快速次序選擇算法 193
10.13 隨機快速次序選擇算法 195
10.14 最壞情況下的綫性選擇算法 197
10.14.1 杠杆點好壞分析 198
10.14.2 算法時間復雜性分析 198
思考題 199
第11章 搜索與散列 201
11.1 搜索問題 202
11.2 順序搜索 203
11.3 摺半搜索 204
11.4 常數搜索 205
11.5 散列搜索 206
11.6 散列函數選擇 207
11.6.1 直接散列 208
11.6.2 除法（模除法）散列 208
11.6.3 乘法散列 209
11.6.4 乘法散列的賭徒原理 210
11.6.5 乘方取中法 211
11.7 散列算法的碰撞問題 211
11.7.1 開放尋址散列 212
11.7.2 開放尋址散列的時間成本 212
11.7.3 開放尋址下成功搜索的時間成本 213
11.7.4 封閉尋址散列 214
11.7.5 探尋序列的設計 215
11.7.6 封閉尋址散列的效率分析 217
11.7.7 搜索不成功的時間成本 217
11.7.8 成功搜索的效率分析 219
11.8 散列錶元素刪除 219
11.9 隨機化散列 220
11.10 全域散列 221
11.11 完美散列 224
思考題 227
第12章 最短路徑 231
12.1 劍指羅馬 231
12.2 最短路徑問題 233
12.3 單源單點最短路徑問題 235
12.3.1 深度優先與廣度優先搜索 235
12.3.2 深度優先解法 237
12.4 單源多點最短路徑問題 238
12.4.1 最短路徑的性質 239
12.4.2 Dijkstra最短路徑算法 240
12.4.3 Dijkstra算法舉例 241
12.4.4 Dijkstra算法與洪水泛濫 242
12.4.5 Dijkstra算法的正確性 243
12.4.6 Dijkstra算法的時間復雜性 245
12.5 Bellman-Ford算法 246
12.5.1 負權重的應對方式 247
12.5.2 Bellman-Ford算法的正確性 250
12.5.3 負循環檢查問題 251
12.5.4 Bellman-Ford算法的時間復雜性 252
12.6 多源多點最短路徑問題 252
12.6.1 多源多點最短路徑問題解決思路 252
12.6.2 直接動態規劃解法 253
12.6.3 矩陣乘法解法 255
12.6.4 Floyd-Warshall算法 255
12.6.5 Johnson算法 256
12.6.6 Johnson等效變換 257
12.6.7 差限問題解決 259
12.7 天意難違 260
思考題 261
第五篇 難解與無解篇
第13章 易解與難解 265
13.1 我們戰無不勝嗎 266
13.2 易解與難解 266
13.3 決策問題和優化問題 267
13.4 決策問題 268
13.5 P類問題 269
13.6 NP類問題 269
13.7 （確定性）圖靈機 270
13.8 非確定性圖靈機 271
13.9 非確定性算法 271
13.10 迴到NP類問題 272
13.11 P和NP 273
13.12 搜索問題、決策問題和優化問題 274
13.13 有沒有解和是否可決定 275
思考題 276
第14章 NP完全問題 277
14.1 玉龍雪山下的審判 277
14.2 NP完全問題的定義 278
14.3 NP完全的重要性 279
14.4 多項式時間規約 280
14.5 如何證明一個問題S是NP完全問題 281
14.6 第1個NP完全問題的證明 281
14.7 庫剋定理 281
14.8 3-SAT問題 284
14.9 證明NP難的技巧 285
14.10 整數規劃 286
14.11 獨立集問題 287
14.12 漢密爾頓迴路問題 289
14.13 討論：弱NP完全、強NP完全和中NP完全 293
思考題 293
第15章 無解與近似 295
15.1 難解問題 296
15.2 不可決定問題 296
15.3 程序終結的判斷 297
15.4 難解之題的求解 298
15.5 智能窮舉、近似算法和本地搜索 299
15.6 智能窮舉之迴溯策略 301
15.7 智能窮舉之分支限界 302
15.8 貪婪近似策略 302
15.9 啓發式搜索策略 303
15.10 模擬退火算法 305
15.10.1 模擬退火算法的思想 306
15.10.2 模擬退火算法的基本循環 306
15.10.3 退火算法描述 307
15.11 基因／遺傳算法 308
15.11.1 生物進化與遺傳 309
15.11.2 遺傳算法的基本要義 309
15.11.3 遺傳算法的實現 310
15.11.4 遺傳算法的基本運算過程 313
15.11.5 遺傳算法的現狀 314
15.12 概率盡在一切中 314
思考題 315
結語 算法之道 317
附錄 算法隨想 321
參考文獻 324
· · · · · · (
收起)
