算法設(shè)計與分析

第1章 算法的基本概念 1
1.1 引言 1
1.1.1 算法的定義和特征 1
1.1.2 算法設(shè)計的例子，窮舉法 3
1.1.3 算法的復(fù)雜性分析 5
1.2 算法的時間復(fù)雜性 6
1.2.1 算法的輸入規(guī)模和運行時間的階 6
1.2.2 運行時間的上界，O記號 9
1.2.3 運行時間的下界，Ω記號 10
1.2.4 運行時間的準(zhǔn)確界，Θ記號 10
1.2.5 復(fù)雜性類型和o記號 13
1.3 算法的時間復(fù)雜性分析 14
1.3.1 循環(huán)次數(shù)的統(tǒng)計 15
1.3.2 基本操作頻率的統(tǒng)計 18
1.3.3 計算步的統(tǒng)計 21
1.3.4 最壞情況和平均情況 22
1.3.5 最壞情況分析 23
1.3.6 平均情況分析 25
1.4 算法的空間復(fù)雜性 28
1.5 最優(yōu)算法 29
習(xí)題 29
參考文獻 31
第2章 常用的數(shù)學(xué)工具 33
2.1 常用的函數(shù)和公式 33
2.1.1 整數(shù)函數(shù) 33
2.1.2 對數(shù)函數(shù) 34
2.1.3 排列、組合和二項式系數(shù) 34
2.1.4 級數(shù)求和 36
2.2 用生成函數(shù)求解遞歸方程 37
2.2.1 生成函數(shù)及其性質(zhì) 37
2.2.2 用生成函數(shù)求解遞歸方程 39
2.3 用特征方程求解遞歸方程 42
2.3.1 k階常系數(shù)線性齊次遞歸方程 43
2.3.2 k階常系數(shù)線性非齊次遞歸方程 45
2.4 用遞推方法求解遞歸方程 48
2.4.1 遞推 48
2.4.2 用遞推法求解變系數(shù)遞歸方程 49
2.4.3 換名 50
習(xí)題 52
參考文獻 53
第3章 排序問題和離散集合的操作 55
3.1 合并排序 55
3.1.1 合并排序算法的實現(xiàn) 55
3.1.2 合并排序算法的分析 57
3.2 基于堆的排序 58
3.2.1 堆 58
3.2.2 堆的操作 59
3.2.3 堆的建立 63
3.2.4 堆的排序 65
3.3 基數(shù)排序 66
3.3.1 基數(shù)排序算法的思想方法 67
3.3.2 基數(shù)排序算法的實現(xiàn) 68
3.3.3 基數(shù)排序算法的分析 70
3.4 離散集合的操作 71
3.4.1 離散集合的數(shù)據(jù)結(jié)構(gòu) 71
3.4.2 union、find操作及路徑壓縮 73
習(xí)題 75
參考文獻 76
第4章 遞歸和分治 78
4.1 基于歸納的遞歸算法 78
4.1.1 歸納法的思想方法 78
4.1.2 遞歸算法的例子 78
4.1.3 多項式求值的遞歸算法 81
4.1.4 排列問題的遞歸算法 82
4.1.5 遞歸算法的討論 83
4.2 分治法 84
4.2.1 分治法引言 84
4.2.2 分治法的設(shè)計原理 87
4.2.3 快速排序 91
4.2.4 多項式乘積的分治算法 96
4.2.5 平面點集最接近點對問題 100
4.2.6 選擇問題 107
習(xí)題 113
參考文獻 114
第5章 貪婪法 115
5.1 貪婪法引言 115
5.1.1 貪婪法的設(shè)計思想 116
5.1.2 貪婪法的例子——貨郎擔(dān)問題 117
5.2 背包問題 118
5.2.1 背包問題貪婪算法的實現(xiàn) 118
5.2.2 背包問題貪婪算法的分析 119
5.3 單源最短路徑問題 120
5.3.1 解最短路徑的狄斯奎諾（Dijkstra）算法 121
5.3.2 狄斯奎諾算法的實現(xiàn) 122
5.3.3 狄斯奎諾算法的分析 124
5.4 最小花費生成樹問題 125
5.4.1 最小花費生成樹引言 125
5.4.2 克魯斯卡爾（Kruskal）算法 126
5.4.3 普里姆（Prim）算法 130
習(xí)題 133
參考文獻 135
第6章 動態(tài)規(guī)劃 136
6.1 動態(tài)規(guī)劃的思想方法 136
6.1.1 動態(tài)規(guī)劃的最優(yōu)決策原理 136
6.1.2 動態(tài)規(guī)劃實例、貨郎擔(dān)問題 137
6.2 多段圖的最短路徑問題 139
6.2.1 多段圖的決策過程 139
6.2.2 多段圖動態(tài)規(guī)劃算法的實現(xiàn) 141
6.3 資源分配問題 143
6.3.1 資源分配的決策過程 143
6.3.2 資源分配算法的實現(xiàn) 146
6.4 設(shè)備更新問題 148
6.4.1 設(shè)備更新問題的決策過程 148
6.4.2 設(shè)備更新算法的實現(xiàn) 150
6.5 最長公共子序列問題 152
6.5.1 最長公共子序列的搜索過程 153
6.5.2 最長公共子序列算法的實現(xiàn) 154
6.6 0/1背包問題 156
6.6.1 0/1背包問題的求解過程 156
6.6.2 0/1背包問題的實現(xiàn) 157
習(xí)題 159
參考文獻 160
第7章 回溯 162
7.1 回溯法的思想方法 162
7.1.1 問題的解空間和狀態(tài)空間樹 162
7.1.2 狀態(tài)空間樹的動態(tài)搜索 163
7.1.3 回溯法的一般性描述 165
7.2 n后問題 168
7.2.1 四后問題的求解過程 168
7.2.2 n后問題算法的實現(xiàn) 169
7.3 圖的著色問題 171
7.3.1 圖著色問題的求解過程 172
7.3.2 圖的m著色問題算法的實現(xiàn) 173
7.4 哈密爾頓回路問題 175
7.4.1 哈密爾頓回路的求解過程 176
7.4.2 哈密爾頓回路算法的實現(xiàn) 176
7.5 0/1背包問題 178
7.5.1 回溯法解0/1背包問題的求解過程 178
7.5.2 回溯法解0/1背包問題算法的實現(xiàn) 181
7.6 回溯法的效率分析 184
習(xí)題 186
參考文獻 187
第8章 分支與限界 188
8.1 分支與限界法的基本思想 188
8.2 貨郎擔(dān)問題 190
8.2.1 費用矩陣的特性及歸約 190
8.2.2 界限的確定和分支的選擇 192
8.2.3 貨郎擔(dān)問題的求解過程 195
8.2.4 幾個輔助函數(shù)的實現(xiàn) 198
8.2.5 貨郎擔(dān)問題分支限界算法的實現(xiàn) 204
8.3 0/1背包問題 206
8.3.1 分支限界法解0/1背包問題的思想方法和求解過程 206
8.3.2 0/1背包問題分支限界算法的實現(xiàn) 208
8.4 作業(yè)分配問題 211
8.4.1 分支限界法解作業(yè)分配問題的思想方法 211
8.4.2 分支限界法解作業(yè)分配問題算法的實現(xiàn) 214
習(xí)題 216
參考文獻 217
第9章 隨機算法 218
9.1 隨機算法引言 218
9.1.1 隨機算法的類型 218
9.1.2 隨機數(shù)發(fā)生器 219
9.2 舍伍德（Sherwood）算法 220
9.2.1 隨機快速排序算法 220
9.2.2 隨機選擇算法 221
9.3 拉斯維加斯（Las Vegas）算法 224
9.3.1 字符串匹配 225
9.3.2 整數(shù)因子 228
9.4 蒙特卡羅（Monte Carlo）算法 229
9.4.1 數(shù)組的主元素問題 230
9.4.2 素數(shù)測試 231
習(xí)題 234
參考文獻 235
第10章 圖和網(wǎng)絡(luò)問題 236
10.1 圖的遍歷 236
10.1.1 圖的深度優(yōu)先搜索遍歷 236
10.1.2 圖的廣度優(yōu)先搜索遍歷 240
10.1.3 無向圖的接合點 243
10.1.4 有向圖的強連通分支 246
10.2 網(wǎng)絡(luò)流量 249
10.2.1 預(yù)備知識 249
10.2.2 Ford_Fulkerson方法和最大容量擴張 251
10.2.3 最短路徑擴張 255
10.3 二分圖的最大匹配問題 258
10.3.1 預(yù)備知識 259
10.3.2 二分圖最大匹配的匈牙利樹方法 260
習(xí)題 266
參考文獻 268
第11章 計算幾何問題 269
11.1 引言 269
11.2 平面線段的交點問題 271
11.2.1 尋找平面線段交點的思想方法 272
11.2.2 尋找平面線段交點的實現(xiàn) 273
11.3 凸殼問題 278
11.3.1 凸殼問題的格雷厄姆（Graham）掃描法 279
11.3.2 格雷厄姆掃描法的實現(xiàn) 280
11.4 平面點集的直徑問題 282
11.4.1 求取平面點集直徑的思想方法 282
11.4.2 平面點集直徑的求取 284
習(xí)題 286
參考文獻 286
第12章 NP完全問題 287
12.1 P類和NP類問題 288
12.1.1 P類問題 288
12.1.2 NP類問題 289
12.2 NP完全問題 291
12.2.1 NP完全問題的定義 291
12.2.2 幾個典型的NP完全問題 292
12.2.3 其他的NP完全問題 298
12.3 co_NP類和NPI類問題 299
習(xí)題 301
參考文獻 302
第13章 計算復(fù)雜性 303
13.1 計算模型 303
13.1.1 圖靈機的基本模型 303
13.1.2 k帶圖靈機和時間復(fù)雜性 306
13.1.3 離線圖靈機和空間復(fù)雜性 308
13.1.4 可滿足性問題和Cook定理 310
13.2 復(fù)雜性類型之間的關(guān)系 313
13.2.1 時間復(fù)雜性和空間復(fù)雜性的關(guān)系 313
13.2.2 時間譜系定理和空間譜系定理 316
13.2.3 填充變元 320
13.3 歸約性關(guān)系 321
13.4 完備性 325
13.4.1 NLOGSPACE完全問題 325
13.4.2 PSPACE完全問題和P完全問題 326
習(xí)題 328
參考文獻 329
第14章 下界 330
14.1 平凡下界 330
14.2 判定樹模型 330
14.2.1 檢索問題 331
14.2.2 排序問題 332
14.3 代數(shù)判定樹模型 333
14.3.1 代數(shù)判定樹模型及下界定理 333
14.3.2 極點問題 335
14.4 線性時間歸約 336
14.4.1 凸殼問題 336
14.4.2 多項式插值問題 337
習(xí)題 338
參考文獻 339
第15章 近似算法 340
15.1 近似算法的性能 340
15.2 裝箱問題 341
15.2.1 首次適宜算法 342
15.2.2 最適宜算法及其他算法 343
15.3 頂點覆蓋問題 344
15.4 貨郎擔(dān)問題 347
15.4.1 歐幾里德貨郎擔(dān)問題 347
15.4.2 一般的貨郎擔(dān)問題 349
15.5 多項式近似方案 350
15.5.1 0/1背包問題的多項式近似方案 350
15.5.2 子集求和問題的完全多項式近似方案 353
習(xí)題 355
參考文獻 356
參考文獻 357