內容簡介
《算法之道》追求的目標是算法背後的邏輯，是一本啟示書，而不是一本包羅萬象的算法大全。因此，《算法之道》甄選了那些最能夠展現算法思想、戰略和精華，並能夠有效訓練算法思維的內容。《算法之道》將算法的討論分為五大部分：算法基礎篇、算法設計篇、算法分析篇、經典算法篇、難解與無解篇。每一個部分分別討論算法的一大方面：基礎、設計、分析、經典和難解問題。
《算法之道》既可以作為大學本科或研究生的算法教材或參考書，也可以作為對算法有興趣的讀者提升認知深度的讀物。
圖書目錄
前言
第一篇 算法基礎篇
第1章 從無有到無窮 2
1.1 意念與現實 3
1.2 什麼是算法 4
1.3 算法的表示 6
1.4 算法之魂 7
1.5 如何比較速度 8
1.6 算法與計算機的關係 9
1.7 算法的範疇 10
1.8 為什麼學習算法 10
思考題 11
第2章 計數與漸近 12
2.1 算法的分析 12
2.1.1 正確性分析 13
2.1.2 時空效率分析 14
2.1.3 時空特性分析 14
2.2 計數：算法分析的核心 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章 動態規劃思想 46
4.1 什麼是動態規劃 47
4.2 流水裝配線問題 48
4.3最長公共子序列52
4.3.1 第一種解法：蠻力策略 52
4.3.2 第二種解法：動態規劃 53
4.4 最長公共子序列變種 55
4.5 記憶遞歸法 55
4.6 空間效率改善 56
4.7 最優二叉搜尋樹 56
4.7.1 遞歸解法 59
4.7.2 計算最優答案 59
4.8 最優子結構與重疊子問題 62
4.8.1 最優子結構 62
4.8.2 重疊子問題 63
4.9 動態規劃與靜態規劃的關係 63
4.10 動態規劃與靜態規劃的相互轉換 64
思考題 65
第5章 貪婪選擇思想 67
5.1 僅有動態規劃是不夠的 67
5.2 什麼是貪婪 68
5.3 背包問題 68
5.4 貪婪選擇屬性 71
5.5 教室規劃問題 72
5.6 最小生成樹 76
5.6.1kruskal算法的正確性 79
5.6.2 Kruskal算法的時間分析 80
5.7Prim算法80
5.8 霍夫曼樹和霍夫曼編碼 83
5.8.1 霍夫曼樹 85
5.8.2 霍夫曼編碼 86
5.8.3 霍夫曼編碼的無前綴編碼性質 87
5.9 貪婪選擇屬性 88
5.10 標準分治、動態規劃和貪婪選擇的比較 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 節點降低算法 103
6.8.3 線性時間最小生成樹算法 104
6.8.4 線性時間最小生成樹算法的時間成本分析 104
6.9 隨機數的生成 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 攤銷分析與數據結構 124
8.3 攤銷分析的幾種方法 124
8.4 聚類分析 125
8.4.1 棧操作的聚類分析 125
8.4.2 二進制計數器的聚類分析 126
8.5 會計分析 128
8.6 勢能分析 130
8.6.1 棧操作的勢能分析 130
8.6.2 二進制計數器的勢能分析 131
8.7 攤銷分析套用：表格擴展的代價 131
8.7.1 動態表插入操作的聚類分析 134
8.7.2 動態表插入操作的會計分析 134
8.7.3 動態表插入操作的勢能分析 136
8.8 運氣不好就攤銷 137
思考題 138
第9章 競爭分析 139
9.1 什麼是競爭分析 139
9.3 競爭力 142
9.4 健忘對手和優良對手 142
9.5 線性表更新問題 143
9.6 前置移動算法的競爭分析 145
9.7 聚類問題 147
9.7.1 聚類問題的次優解算法 148
9.7.2 CLUSTERING-Algorithm算法的競爭分析 148
9.8 競爭分析與普通算法分析 149
思考題 149
第四篇 經典算法篇
第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 計數排序 166
10.9 基數排序 168
10.9.1 基數排序的正確性 169
10.9.2 基數排序的時間效率分析 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 常數搜尋 186
11.5 哈希搜尋 187
11.6 哈希函式選擇 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 深度優先搜尋與廣度優先搜尋 215
12.3.2 深度優先解法 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 負循環檢查問題 231
12.5.4 Bellman-Ford算法的時間複雜性 231
12.6 多源多點最短路徑問題 232
12.6.1 多源多點最短路徑問題解決思路 232
12.6.2 直接動態規劃解法 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 我們戰無不勝嗎 245
13.2 易解與難解 245
13.3 決策問題和最佳化問題 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 搜尋問題、決策問題和最佳化問題 253
13.13 有沒有解和是否可決定 253
思考題 254
第14章 NP完全問題 256
14.1 玉龍雪山下的審判 256
14.2 NP完全問題的定義 257
14.3 NP完全的重要性 258
14.4 多項式時間規約 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 整數規劃 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 啟發式搜尋策略 281
15.10 模擬淬火算法 282
15.10.1 模擬淬火算法的思想 284
15.10.2 模擬淬火算法的基本循環 284
15.10.3 淬火算法描述 284
思考題 286
結語 算法之道 288
附錄 算法隨想 290
參考文獻 293
