第1章　算法：效率、分析和階　　1
1.1　算法　　1
1.2　開發高效算法的重要性　　5
1.2.1　順序查找與二分查找的對比 　　6
1.2.2　斐波那契序列　　7
1.3　算法分析　　10
1.3.1　復雜度分析　　10
1.3.2　理論應用　　14
1.3.3　正確性分析　　15
1.4　階　　15
1.4.1　階的直觀介紹　　15
1.4.2　階數的嚴謹介紹　　17
1.4.3　利用極限計算階　　23
1.5　本書概要　　25
1.6　習題　　25
第2章　分而治之　　30
2.1　二分查找　　30
2.2　閤並排序　　33
2.3　分而治之方法　　38
2.4　快速排序（分割交換排序）　　38
2.5　Strassen矩陣乘法算法　　42
2.6　大整數的算術運算　　46
2.6.1　大整數的錶示：加法和其他綫性時間運算　　46
2.6.2　大整數的乘法　　46
2.7　確定閾值　　50
2.8　不應使用分而治之方法的情況　　53
2.9　習題　　53
第3章　動態規劃　　58
3.1　二項式係數　　58
3.2　Floyd最短路徑算法　　61
3.3　動態規劃與最優化問題　　66
3.4　矩陣鏈乘法　　67
3.5　最優二叉查找樹　　73
3.6　旅行推銷員問題　　79
3.7　序列對準　　84
3.8　習題　　88
第4章　貪婪方法　　92
4.1　最小生成樹　　94
4.1.1　Prim算法　　96
4.1.2　Kruskal算法　　100
4.1.3　Prim算法與Kruskal算法的比較 　　 103
4.1.4　最終討論　　103
4.2　單源最短路徑的Dijkstra算法　　104
4.3　調度計劃　　106
4.3.1　使係統內總時間最短　　106
4.3.2　帶有最終期限的調度安排 　　108
4.4　霍夫曼編碼　　112
4.4.1　前綴碼　　113
4.4.2　霍夫曼算法　　114
4.5　貪婪方法與動態規劃的比較：背包問題 　　 116
4.5.1　0-1背包問題的一種貪婪方法 　　116
4.5.2　部分背包問題的貪婪方法 　　118
4.5.3　0-1背包問題的動態規劃方法 　　118
4.5.4　0-1背包問題動態規劃算法的改進　　118
4.6　習題　　120
第5章　迴溯　　124
5.1　迴溯方法　　124
5.2　n皇後問題　　129
5.3　用濛特卡洛算法估計迴溯算法的效率 132
5.4　“子集之和”問題　　134
5.5　圖的著色　　138
5.6　哈密頓迴路問題　　141
5.7　0-1背包問題　　143
5.7.1　0-1背包問題的迴溯算法 　　143
5.7.2　比較0-1背包問題的動態規劃算法與迴溯算法　　149
5.8　習題　　150
第6章　分支定界　　153
6.1　用0-1背包問題說明分支定界　　154
6.1.1　帶有分支定界修剪的寬度優先查找　　154
6.1.2　帶有分支定界修剪的最佳優先查找　　158
6.2　旅行推銷員問題　　161
6.3　溯因推理（診斷）　　167
6.4　習題　　173
第7章　計算復雜度介紹：排序問題 　　175
7.1　計算復雜度　　175
7.2　插入排序和選擇排序　　176
7.3　每次比較最多減少一個倒置的算法的下限　　179
7.4　再談閤並排序　　181
7.5　再談快速排序　　185
7.6　堆排序　　186
7.6.1　堆和基本堆例程　　186
7.6.2　堆排序的一種實現　　189
7.7　閤並排序、快速排序和堆排序的比較 193
7.8　僅通過鍵的比較進行排序的下限 　　194
7.8.1　排序算法的決策樹　　194
7.8.2　最差情況下的下限　　196
7.8.3　平均情況下的下限　　197
7.9　分配排序（基數排序）　　200
7.10　習題　　203
第8章　再談計算復雜度：查找問題 　　207
8.1　僅通過鍵的比較進行查找的下限 　　207
8.1.1　最差錶現的下限　　209
8.1.2　平均情況下的下限　　210
8.2　插值查找　　213
8.3　樹中的查找　　215
8.3.1　二叉查找樹　　215
8.3.2　B樹　　218
8.4　散列　　219
8.5　選擇問題：對手論證　　222
8.5.1　找齣最大鍵　　222
8.5.2　同時找齣最大鍵和最小鍵 　　223
8.5.3　找齣第二大的鍵　　227
8.5.4　查找第k小的鍵　　230
8.5.5　選擇問題的一種概率算法 　　236
8.6　習題　　238
第9章　計算復雜度和難解性：NP 理論簡介　　241
9.1　難解性　　241
9.2　再談輸入規模　　242
9.3　三類一般問題　　244
9.3.1　已經找到多項式時間算法的問題　　244
9.3.2　已經證明難解的問題　　245
9.3.3　未被證明是難解的，但也從來沒有找到多項式時間算法的問題 　　245
9.4　NP理論　　245
9.4.1　集閤P和NP　　247
9.4.2　NP完全問題　　250
9.4.3　NP睏難、NP容易和NP等價問題 　　 256
9.5　處理NP睏難問題　　259
9.5.1　旅行推銷員問題的近似算法 　　259
9.5.2　裝箱問題的近似算法　　263
9.6　習題　　266
第10章　遺傳算法和遺傳編程　　268
10.1　遺傳知識復習　　268
10.2　遺傳算法　　270
10.2.1　算法　　270
10.2.2　說明範例　　270
10.2.3　旅行推銷員問題　　272
10.3　遺傳編程　　278
10.3.1　說明範例　　279
10.3.2　人造螞蟻　　281
10.3.3　在金融貿易中的應用283
10.4　討論及擴展閱讀　　284
10.5　習題　　284
第11章　數論算法　　286
11.1　數論迴顧　　286
11.1.1　閤數與質數　　286
11.1.2　最大公約數　　286
11.1.3　質因數分解　　288
11.1.4　最小公倍數　　289
11.2　計算最大公約數　　290
11.2.1　歐氏算法　　290
11.2.2　歐氏算法的擴展　　292
11.3　模運算迴顧　　294
11.3.1　群論　　294
11.3.2　關於n同餘　　295
11.3.3　子群　　299
11.4　模綫性方程的求解　　302
11.5　計算模的冪　　305
11.6　尋找大質數　　307
11.6.1　尋找大質數　　307
11.6.2　檢查一個數字是否為質數 　　307
11.7　RSA公鑰密碼係統　　318
11.7.1　公鑰加密係統　　318
11.7.2　RSA加密係統　　319
11.8　習題　　321
第12章　並行算法簡介　　324
12.1　並行體係結構　　325
12.1.1　控製機製　　326
12.1.2　地址空間的組織　　326
12.1.3　互聯網絡　　328
12.2　PRAM模型　　330
12.2.1　為CREW PRAM模型設計算法 　　 332
12.2.2　為CRCW PRAM模型設計算法 　　 337
12.3　習題　　339
附錄A　必備數學知識迴顧　　340
附錄B　求解遞歸方程：在遞歸算法分析中的應用　　363
附錄C　不交集的數據結構　　388
參考文獻　　395
· · · · · · (收起)