算法設(shè)計(jì)與分析（第3版）

目 錄
第1篇 算法設(shè)計(jì)與分析的基本概念

第1章 算法的基本概念 2
1.1 引言 2
1.1.1 算法的定義和特征 2
1.1.2 算法設(shè)計(jì)的例子——窮舉法 4
1.1.3 算法的復(fù)雜性分析 7
1.2 算法的時(shí)間復(fù)雜性 8
1.2.1 算法的輸入規(guī)模和運(yùn)行時(shí)間的階 8
1.2.2 運(yùn)行時(shí)間的上界——O記號(hào) 11
1.2.3 運(yùn)行時(shí)間的下界——Ω記號(hào) 12
1.2.4 運(yùn)行時(shí)間的準(zhǔn)確界——Θ記號(hào) 13
1.2.5 O記號(hào)、Ω記號(hào)、Θ記號(hào)的性質(zhì) 17
1.2.6 復(fù)雜性類(lèi)型和o記號(hào) 18
習(xí)題 19
參考文獻(xiàn) 20

第2章 算法的復(fù)雜性分析 21
2.1 常用的函數(shù)和公式 21
2.1.1 整數(shù)函數(shù) 21
2.1.2 對(duì)數(shù)函數(shù) 22
2.1.3 排列、組合和二項(xiàng)式系數(shù) 23
2.1.4 級(jí)數(shù)求和 24
2.2 算法的時(shí)間復(fù)雜性分析 25
2.2.1 循環(huán)次數(shù)的統(tǒng)計(jì) 26
2.2.2 基本操作頻率的統(tǒng)計(jì) 29
2.2.3 計(jì)算步的統(tǒng)計(jì) 32
2.3 最好情況、最壞情況和平均情況分析 33
2.3.1 最好情況、最壞情況和平均情況 33
2.3.2 最好情況和最壞情況分析 34
2.3.3 平均情況分析 37

2.4 用生成函數(shù)求解遞歸方程 40
2.4.1 生成函數(shù)及其性質(zhì) 40
2.4.2 用生成函數(shù)求解遞歸方程 43
2.5 用特征方程求解遞歸方程 46
2.5.1 k階常系數(shù)線性齊次遞歸方程 47
2.5.2 k階常系數(shù)線性非齊次遞歸方程 49
2.6 用遞推方法求解遞歸方程 51
2.6.1 遞推 52
2.6.2 用遞推法求解變系數(shù)遞歸方程 52
2.6.3 換名 54
2.7 算法的空間復(fù)雜性 56
2.8 最優(yōu)算法 57
習(xí)題 58
參考文獻(xiàn) 60

第2篇 算法設(shè)計(jì)的基本技術(shù)

第3章 排序問(wèn)題和離散集合的操作 62
3.1 合并排序 62
3.1.1 合并排序算法的實(shí)現(xiàn) 62
3.1.2 合并排序算法的分析 64
3.2 基于堆的排序 65
3.2.1 堆 66
3.2.2 堆的操作 67
3.2.3 堆的建立 70
3.2.4 堆的排序 73
3.3 基數(shù)排序 74
3.3.1 基數(shù)排序算法的思想方法 74
3.3.2 基數(shù)排序算法的實(shí)現(xiàn) 76
3.3.3 基數(shù)排序算法的分析 78
3.4 離散集合的Union_Find操作 79
3.4.1 用于Union_Find操作的數(shù)據(jù)結(jié)構(gòu) 79
3.4.2 union、find操作及路徑壓縮 81
習(xí)題 84
參考文獻(xiàn) 85

第4章 遞歸和分治 86
4.1 基于歸納的遞歸算法 86
4.1.1 基于歸納的遞歸算法的思想方法 86
4.1.2 遞歸算法的例子 87
4.1.3 排列問(wèn)題的遞歸算法 91
4.1.4 求數(shù)組主元素的遞歸算法 95
4.1.5 整數(shù)劃分問(wèn)題的遞歸算法 98
4.2 分治法 100
4.2.1 分治法的例子 100
4.2.2 分治法的設(shè)計(jì)原理 104
4.2.3 快速排序 111
4.2.4 多項(xiàng)式乘積和大整數(shù)乘法 116
4.2.5 平面點(diǎn)集最接近點(diǎn)對(duì)問(wèn)題 123
4.2.6 選擇問(wèn)題 130
4.2.7 殘缺棋盤(pán)問(wèn)題 136
習(xí)題 141
參考文獻(xiàn) 143

第5章 貪婪法 145
5.1 貪婪法概述 146
5.1.1 貪婪法的設(shè)計(jì)思想 146
5.1.2 貪婪法的例子——貨郎擔(dān)問(wèn)題 147
5.2 背包問(wèn)題 148
5.2.1 背包問(wèn)題貪婪算法的實(shí)現(xiàn) 148
5.2.2 背包問(wèn)題貪婪算法的分析 150
5.3 單源最短路徑問(wèn)題 151
5.3.1 解最短路徑的狄斯奎諾算法 151
5.3.2 狄斯奎諾算法的實(shí)現(xiàn) 153
5.3.3 狄斯奎諾算法的分析 155
5.4 最小花費(fèi)生成樹(shù)問(wèn)題 156
5.4.1 最小花費(fèi)生成樹(shù)概述 156
5.4.2 克魯斯卡爾算法 157
5.4.3 普里姆算法 161
5.5 霍夫曼編碼問(wèn)題 165
5.5.1 前綴碼和最優(yōu)二叉樹(shù) 165
5.5.2 霍夫曼編碼的實(shí)現(xiàn) 169
習(xí)題 171
參考文獻(xiàn) 173

第6章 動(dòng)態(tài)規(guī)劃 174
6.1 動(dòng)態(tài)規(guī)劃的思想方法 174
6.1.1 動(dòng)態(tài)規(guī)劃的最優(yōu)決策原理 174
6.1.2 動(dòng)態(tài)規(guī)劃實(shí)例——貨郎擔(dān)問(wèn)題 175
6.2 多段圖的最短路徑問(wèn)題 177
6.2.1 多段圖的決策過(guò)程 178
6.2.2 多段圖動(dòng)態(tài)規(guī)劃算法的實(shí)現(xiàn) 180
6.3 資源分配問(wèn)題 181
6.3.1 資源分配的決策過(guò)程 182
6.3.2 資源分配算法的實(shí)現(xiàn) 184
6.4 設(shè)備更新問(wèn)題 187
6.4.1 設(shè)備更新問(wèn)題的決策過(guò)程 187
6.4.2 設(shè)備更新算法的實(shí)現(xiàn) 190
6.5 最長(zhǎng)公共子序列問(wèn)題 192
6.5.1 最長(zhǎng)公共子序列的搜索過(guò)程 192
6.5.2 最長(zhǎng)公共子序列算法的實(shí)現(xiàn) 195
6.6 0/1背包問(wèn)題 196
6.6.1 0/1背包問(wèn)題的求解過(guò)程 196
6.6.2 0/1背包問(wèn)題的實(shí)現(xiàn) 198
6.7 RNA最大堿基對(duì)匹配問(wèn)題 199
6.7.1 RNA最大堿基對(duì)匹配的搜索過(guò)程 200
6.7.2 RNA最大堿基對(duì)匹配算法的實(shí)現(xiàn) 203
習(xí)題 205
參考文獻(xiàn) 207

第7章 回溯 208
7.1 回溯法的思想方法 208
7.1.1 問(wèn)題的解空間和狀態(tài)空間樹(shù) 208
7.1.2 狀態(tài)空間樹(shù)的動(dòng)態(tài)搜索 209
7.1.3 回溯法的一般性描述 211
7.2 n皇后問(wèn)題 213
7.2.1 n皇后問(wèn)題的求解過(guò)程 213
7.2.2 n皇后問(wèn)題算法的實(shí)現(xiàn) 215
7.3 圖的著色問(wèn)題 217
7.3.1 圖著色問(wèn)題的求解過(guò)程 218
7.3.2 圖的m著色問(wèn)題算法的實(shí)現(xiàn) 220
7.4 哈密爾頓回路問(wèn)題 222
7.4.1 哈密爾頓回路的求解過(guò)程 222
7.4.2 哈密爾頓回路算法的實(shí)現(xiàn) 224
7.5 0/1背包問(wèn)題 225
7.5.1 回溯法解0/1背包問(wèn)題的求解過(guò)程 226
7.5.2 回溯法解0/1背包問(wèn)題算法的實(shí)現(xiàn) 229
7.6 回溯法的效率分析 231
習(xí)題 234
參考文獻(xiàn) 235

第8章 分支與限界 236
8.1 分支與限界法的基本思想 236
8.2 作業(yè)分配問(wèn)題 238
8.2.1 分支限界法解作業(yè)分配問(wèn)題的思想方法 238
8.2.2 分支限界法解作業(yè)分配問(wèn)題算法的實(shí)現(xiàn) 241
8.3 單源最短路徑問(wèn)題 244
8.3.1 分支限界法解單源最短路徑問(wèn)題的思想方法 244
8.3.2 分支限界法解單源最短路徑問(wèn)題算法的實(shí)現(xiàn) 246
8.4 0/1背包問(wèn)題 248
8.4.1 分支限界法解0/1背包問(wèn)題的思想方法和求解過(guò)程 249
8.4.2 0/1背包問(wèn)題分支限界算法的實(shí)現(xiàn) 251
8.5 貨郎擔(dān)問(wèn)題 254
8.5.1 費(fèi)用矩陣的特性及歸約 254
8.5.2 界限的確定和分支的選擇 256
8.5.3 貨郎擔(dān)問(wèn)題的求解過(guò)程 259
8.5.4 幾個(gè)輔助函數(shù)的實(shí)現(xiàn) 262
8.5.5 貨郎擔(dān)問(wèn)題分支限界算法的實(shí)現(xiàn) 268
習(xí)題 271
參考文獻(xiàn) 272

第9章 隨機(jī)算法 273
9.1 隨機(jī)算法概述 273
9.1.1 隨機(jī)算法的類(lèi)型 273
9.1.2 隨機(jī)數(shù)發(fā)生器 274
9.2 舍伍德算法 275
9.2.1 隨機(jī)快速排序算法 275
9.2.2 隨機(jī)選擇算法 277
9.3 拉斯維加斯算法 280
9.3.1 字符串匹配 280
9.3.2 整數(shù)因子 284
9.4 蒙特卡羅算法 285
9.4.1 數(shù)組的主元素問(wèn)題 285
9.4.2 素?cái)?shù)測(cè)試 287
習(xí)題 290
參考文獻(xiàn) 291

第3篇 計(jì)算機(jī)應(yīng)用領(lǐng)域的一些基法

第10章 圖和網(wǎng)絡(luò)問(wèn)題 294
10.1 圖的遍歷 294
10.1.1 圖的深度優(yōu)先搜索遍歷 294
10.1.2 圖的廣度優(yōu)先搜索遍歷 299
10.1.3 無(wú)向圖的接合點(diǎn) 301
10.1.4 有向圖的強(qiáng)連通分支 305
10.2 網(wǎng)絡(luò)流 308
10.2.1 網(wǎng)絡(luò)流的概念 308
10.2.2 Ford_Fulkerson方法和最大容量增廣 312
10.2.3 最短路徑增廣 315
10.3 二分圖的最大匹配問(wèn)題 320
10.3.1 預(yù)備知識(shí) 321
10.3.2 二分圖最大匹配的匈牙利樹(shù)方法 323
習(xí)題 329
參考文獻(xiàn) 331

第11章 計(jì)算幾何問(wèn)題 332
11.1 引言 332
11.2 平面線段的交點(diǎn)問(wèn)題 334
11.2.1 尋找平面線段交點(diǎn)的思想方法 335
11.2.2 尋找平面線段交點(diǎn)的實(shí)現(xiàn) 337
11.3 凸殼問(wèn)題 342
11.3.1 凸殼問(wèn)題的格雷厄姆掃描法 343
11.3.2 格雷厄姆掃描法的實(shí)現(xiàn) 344
11.4 平面點(diǎn)集的直徑問(wèn)題 346
11.4.1 求取平面點(diǎn)集直徑的思想方法 346
11.4.2 平面點(diǎn)集直徑的求取 348
習(xí)題 350
參考文獻(xiàn) 351

第4篇 算法設(shè)計(jì)與分析的一些理論問(wèn)題

第12章 NP完全問(wèn)題 354
12.1 P類(lèi)和NP類(lèi)問(wèn)題 355
12.1.1 P類(lèi)問(wèn)題 355
12.1.2 NP類(lèi)問(wèn)題 356
12.2 NP完全問(wèn)題 358
12.2.1 NP完全問(wèn)題的定義 358
12.2.2 幾個(gè)典型的NP完全問(wèn)題 360
12.2.3 其他NP完全問(wèn)題 366
12.3 co_NP類(lèi)和NPI類(lèi)問(wèn)題 366
習(xí)題 369
參考文獻(xiàn) 370

第13章 計(jì)算復(fù)雜性 371
13.1 計(jì)算模型 371
13.1.1 圖靈機(jī)的基本模型 371
13.1.2 k帶圖靈機(jī)和時(shí)間復(fù)雜性 374
13.1.3 離線圖靈機(jī)和空間復(fù)雜性 376
13.1.4 可滿足性問(wèn)題和Cook定理 379
13.2 復(fù)雜性類(lèi)型之間的關(guān)系 381
13.2.1 時(shí)間復(fù)雜性和空間復(fù)雜性的關(guān)系 382
13.2.2 時(shí)間譜系定理和空間譜系定理 384
13.2.3 填充變?cè)?389
13.3 歸約性關(guān)系 391
13.4 完備性 394
13.4.1 NLOGSPACE完全問(wèn)題 394
13.4.2 PSPACE完全問(wèn)題和P完全問(wèn)題 396
習(xí)題 397
參考文獻(xiàn) 398

第14章 下界 399
14.1 平凡下界 399
14.2 判定樹(shù)模型 399
14.2.1 檢索問(wèn)題 400
14.2.2 排序問(wèn)題 401
14.3 代數(shù)判定樹(shù)模型 402
14.3.1 代數(shù)判定樹(shù)模型及下界定理 402
14.3.2 極點(diǎn)問(wèn)題 404
14.4 線性時(shí)間歸約 405
14.4.1 凸殼問(wèn)題 406
14.4.2 多項(xiàng)式插值問(wèn)題 406
習(xí)題 408
參考文獻(xiàn) 408

第15章 近似算法 409
15.1 近似算法的性能 409
15.2 裝箱問(wèn)題 410
15.2.1 首次適宜算法 411
15.2.2 最適宜算法及其他算法 412
15.3 頂點(diǎn)覆蓋問(wèn)題 414
15.4 貨郎擔(dān)問(wèn)題 416
15.4.1 歐幾里得貨郎擔(dān)問(wèn)題 417
15.4.2 一般的貨郎擔(dān)問(wèn)題 419
15.5 多項(xiàng)式近似方案 419
15.5.1 0/1背包問(wèn)題的多項(xiàng)式近似方案 420
15.5.2 子集求和問(wèn)題的完全多項(xiàng)式近似方案 423
習(xí)題 425
參考文獻(xiàn) 426

參考文獻(xiàn) 427