算法之道

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