算法設(shè)計(jì)與分析基礎(chǔ)（第3版 詳解版）

詳細(xì)目錄
第1章　導(dǎo)言 1
1.1　什么是算法 3
習(xí)題1.1 8
1.2　算法問題求解基礎(chǔ) 9
1.2.1  理解問題 10
1.2.2  了解計(jì)算設(shè)備的性能 11
1.2.3  在精確和近似解法之間做出選擇 12
1.2.4  算法的設(shè)計(jì)技術(shù) 12
1.2.5  設(shè)計(jì)算法和數(shù)據(jù)結(jié)構(gòu) 12
1.2.6  算法描述方法 13
1.2.7  算法的正確性證明 14
1.2.8  分析算法 14
1.2.9  為算法寫代碼 16
習(xí)題1.2 17
1.3　重要的問題類型 19
1.3.1  排序 19
1.3.2  查找 21
1.3.3  字符串處理 21
1.3.4  圖問題 22
1.3.5  組合問題 22
1.3.6  幾何問題 23
1.3.7  數(shù)值問題 23
習(xí)題1.3 24
1.4　基本數(shù)據(jù)結(jié)構(gòu) 26
1.4.1  線性數(shù)據(jù)結(jié)構(gòu) 26
1.4.2  圖 29
1.4.3  樹 32
1.4.4  集合與字典 36
習(xí)題1.4 38
本章要點(diǎn)小結(jié) 39
第2章　算法效率分析基礎(chǔ) 41
2.1　分析框架 42
2.1.1  度量輸入規(guī)模 43
2.1.2  運(yùn)行時(shí)間的度量單位 44
2.1.3  增長量級(jí) 45
2.1.4  算法的最差、最優(yōu)和平均效率 47
2.1.5  分析框架概要 50
習(xí)題2.1 50
2.2　漸近符號(hào)和基本效率類型 52
2.2.1  非正式的介紹 53
2.2.2  符號(hào)O 53
2.2.3  符號(hào)Ω 54
2.2.4  符號(hào)Θ 55
2.2.5  漸近符號(hào)的有用特性 56
2.2.6  利用極限比較增長量級(jí) 57
2.2.7  基本效率類別 58
習(xí)題2.2 60
2.3  非遞歸算法的數(shù)學(xué)分析 61
習(xí)題2.3 67
2.4  遞歸算法的數(shù)學(xué)分析 70
習(xí)題2.4 77
2.5　例題：計(jì)算第n個(gè)斐波那契數(shù) 80
習(xí)題2.5 84
2.6　算法的經(jīng)驗(yàn)分析 85
習(xí)題2.6 91
2.7　算法可視化 92
本章要點(diǎn)小結(jié) 95
第3章　蠻力法 97
3.1　選擇排序和冒泡排序 98
3.1.1  選擇排序 98
3.1.2  冒泡排序 100
習(xí)題3.1 102
3.2　順序查找和蠻力字符串匹配 103
3.2.1  順序查找 104
3.2.2  蠻力字符串匹配 104
習(xí)題3.2 106
3.3　最近對(duì)和凸包問題的蠻力算法 108
3.3.1  最近對(duì)問題 108
3.3.2  凸包問題 110
習(xí)題3.3 113
3.4　窮舉查找 115
3.4.1  旅行商問題 116
3.4.2  背包問題 117
3.4.3  分配問題 119
習(xí)題3.4 120
3.5　深度優(yōu)先查找和廣度優(yōu)先查找 122
3.5.1  深度優(yōu)先查找 122
3.5.2  廣度優(yōu)先查找 125
習(xí)題3.5 128
本章要點(diǎn)小結(jié) 130
第4章　減治法 132
4.1　插入排序 135
習(xí)題4.1 137
4.2　拓?fù)渑判?140
習(xí)題4.2 143
4.3  生成組合對(duì)象的算法 145
4.3.1  生成排列 145
4.3.2  生成子集 148
習(xí)題4.3 150
4.4  減常因子算法 151
4.4.1  折半查找 152
4.4.2  假幣問題 154
4.4.3  俄式乘法 155
4.4.4  約瑟夫斯問題 156
習(xí)題4.4 158
4.5　減可變規(guī)模算法 160
4.5.1  計(jì)算中值和選擇問題 160
4.5.2  插值查找 164
4.5.3  二叉查找樹的查找和插入 165
4.5.4  尼姆游戲 166
習(xí)題4.5 168
本章要點(diǎn)小結(jié) 170
第5章　分治法 171
5.1　合并排序 173
習(xí)題5.1 176
5.2　快速排序 178
習(xí)題5.2 183
5.3　二叉樹遍歷及其相關(guān)特性 185
習(xí)題5.3 188
5.4　大整數(shù)乘法和Strassen矩陣乘法 189
5.4.1  大整數(shù)乘法 190
5.4.2  Strassen矩陣乘法 192
習(xí)題5.4 194
5.5　用分治法解最近對(duì)問題和凸包問題 195
5.5.1  最近對(duì)問題 195
5.5.2  凸包問題 198
習(xí)題5.5 200
本章要點(diǎn)小結(jié) 201
第6章　變治法 203
6.1　預(yù)排序 204
習(xí)題6.1 207
6.2　高斯消去法 210
6.2.1  LU分解 215
6.2.2  計(jì)算矩陣的逆 216
6.2.3  計(jì)算矩陣的行列式 217
習(xí)題6.2 218
6.3　平衡查找樹 220
6.3.1  平衡二叉查找樹 221
6.3.2  2-3樹 225
習(xí)題6.3 228
6.4　堆和堆排序 229
6.4.1  堆的概念 229
6.4.2  堆排序 234
習(xí)題6.4 235
6.5　霍納法則和二進(jìn)制冪 236
6.5.1  霍納法則 237
6.5.2  二進(jìn)制冪 239
習(xí)題6.5 242
6.6　問題化簡(jiǎn) 243
6.6.1  求最小公倍數(shù) 244
6.6.2  計(jì)算圖中的路徑數(shù)量 245
6.6.3  最優(yōu)化問題的化簡(jiǎn) 246
6.6.4  線性規(guī)劃 247
6.6.5  簡(jiǎn)化為圖問題 250
習(xí)題6.6 251
本章要點(diǎn)小結(jié) 253
第7章　時(shí)空權(quán)衡 255
7.1　計(jì)數(shù)排序 256
習(xí)題7.1 260
7.2　字符串匹配中的輸入增強(qiáng)技術(shù) 261
7.2.1　Horspool算法 262
7.2.2　Boyer-Moore算法 265
習(xí)題7.2 270
7.3　散列法 271
7.3.1　開散列(分離鏈) 273
7.3.2　閉散列(開式尋址) 275
習(xí)題7.3 278
7.4　B樹 279
習(xí)題7.4 283
本章要點(diǎn)小結(jié) 284
第8章　動(dòng)態(tài)規(guī)劃 285
8.1　三個(gè)基本例子 287
習(xí)題8.1 292
8.2　背包問題和記憶功能 295
8.2.1  背包問題 295
8.2.2　記憶功能 297
習(xí)題8.2 298
8.3　最優(yōu)二叉查找樹 299
習(xí)題8.3 304
8.4　Warshall算法和Floyd算法 305
8.4.1　Warshall算法 306
8.4.2　計(jì)算完全最短路徑的Floyd算法 309
習(xí)題8.4 313
本章要點(diǎn)小結(jié) 314
第9章　貪婪技術(shù) 315
9.1　Prim算法 318
習(xí)題9.1 323
9.2　Kruskal算法 325
習(xí)題9.2 332
9.3　Dijkstra算法 334
習(xí)題9.3 338
9.4　哈夫曼樹及編碼 339
習(xí)題9.4 343
本章要點(diǎn)小結(jié) 344
第10章　迭代改進(jìn) 346
10.1　單純形法 347
10.1.1  線性規(guī)劃的幾何解釋 348
10.1.2  單純形法概述 352
10.1.3  單純形法其他要點(diǎn) 358
習(xí)題10.1 360
10.2　最大流量問題 362
習(xí)題10.2 372
10.3　二分圖的最大匹配 373
習(xí)題10.3 380
10.4　穩(wěn)定婚姻問題 382
習(xí)題10.4 386
本章要點(diǎn)小結(jié) 387
第11章　算法能力的極限 388
11.1　如何求下界 389
11.1.1　平凡下界 390
11.1.2　信息論下界 391
11.1.3　敵手下界 391
11.1.4　問題化簡(jiǎn) 393
習(xí)題11.1 394
11.2　決策樹 396
11.2.1　排序的決策樹 397
11.2.2　查找有序數(shù)組的決策樹 399
習(xí)題11.2 401
11.3　P、NP和NP完全問題 403
11.3.1　P和NP問題 403
11.3.2　NP完全問題 407
習(xí)題11.3 411
11.4　數(shù)值算法的挑戰(zhàn) 414
習(xí)題11.4 421
本章要點(diǎn)小結(jié) 422
第12章　應(yīng)對(duì)算法能力的極限 425
12.1　回溯法 426
12.1.1　n皇后問題 427
12.1.2　哈密頓回路問題 428
12.1.3　子集和問題 429
12.1.4　概括性說明 430
習(xí)題12.1 432
12.2　分支定界法 434
12.2.1　分配問題 435
12.2.2　背包問題 437
12.2.3　旅行商問題 440
習(xí)題12.2 442
12.3　NP難題的近似算法 443
12.3.1　旅行商問題的近似算法 445
12.3.2　背包問題的近似算法 454
習(xí)題12.3 459
12.4　解非線性方程的算法 460
12.4.1　對(duì)分法 462
12.4.2　試位法 465
12.4.3　牛頓法 466
習(xí)題12.4 468
本章要點(diǎn)小結(jié) 469
后記 472
附錄A　算法分析的實(shí)用公式 477
附錄B　遞推關(guān)系簡(jiǎn)明指南 480
參考文獻(xiàn) 494