《算法設計與分析》系統(tǒng)地介紹了算法設計與分析的概念和方法，共4篇內(nèi)容。第1篇介紹算法設計與分析的基本概念，結合窮舉法、排序問題及其他一些算法，對算法的時間復雜性的概念及復雜性的分析方法作了較為詳細的敘述；第2篇以算法設計技術為綱，從合并排序、堆排序、離散集合的union和find操作開始，進而介紹遞歸技術、分治法、貪婪法、動態(tài)規(guī)劃、回溯法、分支與限界法和隨機算法等算法設計技術及其復雜性分析；第3篇介紹計算機應用領域里的一些算法，如圖和網(wǎng)絡流，以及計算幾何中的一些問題；第4篇介紹算法設計與分析中的一些理論問題，如NP完全問題、計算復雜性問題、下界理論問題，最后介紹近似算法及其性能分析。
《算法設計與分析》內(nèi)容選材適當、編排合理、由淺入深、循序漸進、互相銜接、逐步展開，并附有大量實例，既注重算法的思想方法、推導過程和正確性的證明技術，也注重算法所涉及的數(shù)據(jù)結構、算法的具體實現(xiàn)和算法的工作過程。
《算法設計與分析》可作為高等院校計算機專業(yè)本科生和研究生的教材，也可作為計算機科學與應用的科學技術人員的參考資料。
《算法設計與分析》內(nèi)容選材適當、編排合理、逐步展開，是高等院校計算機專業(yè)本科生和研究生必選的教材。
前 言
計算機系統(tǒng)中的任何軟件，都是按特定的算法來予以實現(xiàn)的。算法性能的好壞，直接決定了所實現(xiàn)軟件性能的優(yōu)劣。如何判定一個算法的性能？用什么方法來設計算法？所設計的算法需要多少運行時間、多少存儲空間？在實現(xiàn)一個軟件時，這些都是必須予以解決的問題。計算機中的操作系統(tǒng)、語言編譯系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)，以及各種各樣的計算機應用系統(tǒng)中的軟件，都離不開用具體的算法來實現(xiàn)。因此，算法設計與分析是計算機科學與技術的一個核心問題，也是大學計算機專業(yè)本科生及研究生必修的一門重要的專業(yè)基礎課程。通過算法設計與分析這門課程的學習，讀者能夠掌握算法設計與分析的方法，并利用這些方法去解決在計算機科學與技術中所遇到的各種問題，設計計算機系統(tǒng)的各種軟件中所可能遇到的算法，并對所設計的算法做出科學的評價。因此，算法設計與分析，不僅對計算機專業(yè)的科學技術人員，而且對使用計算機的其他專業(yè)技術人員，都是非常重要的。
本書內(nèi)容選材適當、編排合理、由淺入深、循序漸進、互相銜接、逐步展開，在編寫過程中，盡可能遵循下面幾個原則。
（1）面對學生，盡可能用通俗的語言來表達深奧的問題。因此，公式推導盡可能詳盡，因為這樣才不會為難學生；所用到的專門術語或知識來龍去脈盡可能介紹清楚，因為這樣，學生才不會感到錯愕和不知所措；對問題的敘述，盡可能開門見山，使學生能較快地、容易地接觸到問題的實質(zhì)。
（2）實現(xiàn)算法的思想方法和推導過程盡可能詳細和易于理解，因為這樣，學生才能深刻地理解和掌握算法的工作原理。
（3）對算法的某些理論基礎和定理的證明給予足夠的重視，定義的敘述盡可能嚴謹，方法推導、定理證明的邏輯盡可能嚴密，因為這可以培養(yǎng)學生良好的邏輯思維能力和嚴謹規(guī)范的科學方法，而設計并實現(xiàn)一個算法，具有良好的邏輯思維能力和嚴謹規(guī)范的科學方法是很重要的。
（4）算法具體實現(xiàn)的描述、所涉及的數(shù)據(jù)結構和變量，都做出較為詳盡的說明。因為有些學生盡管知道了思想方法，也了解了實現(xiàn)步驟，但具體實現(xiàn)起來，有時卻覺得束手無策。對算法的具體實現(xiàn)和所用到的數(shù)據(jù)結構的較為詳細的描述，可以培養(yǎng)學生的具體實踐能力，使學生學會如何使用所學過的知識來設計和實現(xiàn)某些算法。
（5）算法的工作過程，盡可能詳細說明。對工作過程中比較難于理解的某些算法，則通過實例，從頭到尾地模擬算法的運行。因為這是學習、理解算法的關鍵，沒有用實例來模擬算法的運行，學生學完了以后，對該算法也只能是懵懂的，不知其所以然。
（6）無論是算法的基本概念、算法復雜性的分析方法，還是算法的實現(xiàn)步驟，都盡可能提供大量實例加以解釋說明。
本書先以最簡單的窮舉法為例，說明算法設計技術及算法分析的重要性；接著以排序問題中的一些基本算法和其他一些算法為例，說明算法復雜性的一般分析方法；然后以算法設計技術為綱，按照實現(xiàn)算法的思想方法、實現(xiàn)步驟、所涉及的數(shù)據(jù)結構、算法的具體描述及復雜性分析等幾個方面，逐個介紹各種算法設計技術及其分析方法。
全書分為4篇。第1篇包括第1章和第2章，介紹算法設計與分析的基本概念。第1章介紹算法的定義及算法的時間復雜性的基本概念；第2章介紹算法時間復雜性的分析方法，并簡單介紹與算法分析有關的最基本的數(shù)學工具。第2篇包括第3~9章，介紹算法設計的基本技術。第3章繼續(xù)介紹排序問題和離散集合的操作，進一步對算法分析進行了闡述，并為下面各章中所涉及的問題作了技術上的準備；第4章介紹遞歸技術及分治方法，從理論上分析了分治算法的效率；第5章介紹貪婪法的設計方法及其正確性的證明；第6章介紹動態(tài)規(guī)劃法的設計技術；第7章介紹回溯法的設計技術；第8章在回溯法的基礎上介紹分支與限界方法的應用及其分析；第9章介紹3種類型的隨機算法及其性能分析。第3篇包括第10~11章，涉及計算機應用領域里的一些算法。第10章介紹圖和網(wǎng)絡流的一些問題；第11章介紹計算幾何中的一些問題。第4篇包括第12~15章，介紹算法設計與分析中的一些理論問題。第12章介紹NP完全問題；第13章介紹計算復雜性問題；第14章介紹下界理論問題；第15章介紹近似算法及其性能分析。
本書對第2版做了一些修訂。感謝許存權、鐘志芳、紀文遠、蘇明芳、鄧艷諸位編輯為本書的出版付出的大量工作和努力，在此表示誠摯的謝意。
由于水平有限，書中難免存在不當之處，敬請讀者指正。
編 者
目 錄
第1篇 算法設計與分析的基本概念
第1章 算法的基本概念 2
1.1 引言 2
1.1.1 算法的定義和特征 2
1.1.2 算法設計的例子——窮舉法 4
1.1.3 算法的復雜性分析 7
1.2 算法的時間復雜性 8
1.2.1 算法的輸入規(guī)模和運行時間的階 8
1.2.2 運行時間的上界——O記號 11
1.2.3 運行時間的下界——Ω記號 12
1.2.4 運行時間的準確界——Θ記號 13
1.2.5 O記號、Ω記號、Θ記號的性質(zhì) 17
1.2.6 復雜性類型和o記號 18
習題 19
參考文獻 20
第2章 算法的復雜性分析 21
2.1 常用的函數(shù)和公式 21
2.1.1 整數(shù)函數(shù) 21
2.1.2 對數(shù)函數(shù) 22
2.1.3 排列、組合和二項式系數(shù) 23
2.1.4 級數(shù)求和 24
2.2 算法的時間復雜性分析 25
2.2.1 循環(huán)次數(shù)的統(tǒng)計 26
2.2.2 基本操作頻率的統(tǒng)計 29
2.2.3 計算步的統(tǒng)計 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 算法的空間復雜性 56
2.8 最優(yōu)算法 57
習題 58
參考文獻 60
第2篇 算法設計的基本技術
第3章 排序問題和離散集合的操作 62
3.1 合并排序 62
3.1.1 合并排序算法的實現(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ù)排序算法的實現(xiàn) 76
3.3.3 基數(shù)排序算法的分析 78
3.4 離散集合的Union_Find操作 79
3.4.1 用于Union_Find操作的數(shù)據(jù)結構 79
3.4.2 union、find操作及路徑壓縮 81
習題 84
參考文獻 85
第4章 遞歸和分治 86
4.1 基于歸納的遞歸算法 86
4.1.1 基于歸納的遞歸算法的思想方法 86
4.1.2 遞歸算法的例子 87
4.1.3 排列問題的遞歸算法 91
4.1.4 求數(shù)組主元素的遞歸算法 95
4.1.5 整數(shù)劃分問題的遞歸算法 98
4.2 分治法 100
4.2.1 分治法的例子 100
4.2.2 分治法的設計原理 104
4.2.3 快速排序 111
4.2.4 多項式乘積和大整數(shù)乘法 116
4.2.5 平面點集最接近點對問題 123
4.2.6 選擇問題 130
4.2.7 殘缺棋盤問題 136
習題 141
參考文獻 143
第5章 貪婪法 145
5.1 貪婪法概述 146
5.1.1 貪婪法的設計思想 146
5.1.2 貪婪法的例子——貨郎擔問題 147
5.2 背包問題 148
5.2.1 背包問題貪婪算法的實現(xiàn) 148
5.2.2 背包問題貪婪算法的分析 150
5.3 單源最短路徑問題 151
5.3.1 解最短路徑的狄斯奎諾算法 151
5.3.2 狄斯奎諾算法的實現(xiàn) 153
5.3.3 狄斯奎諾算法的分析 155
5.4 最小花費生成樹問題 156
5.4.1 最小花費生成樹概述 156
5.4.2 克魯斯卡爾算法 157
5.4.3 普里姆算法 161
5.5 霍夫曼編碼問題 165
5.5.1 前綴碼和最優(yōu)二叉樹 165
5.5.2 霍夫曼編碼的實現(xiàn) 169
習題 171
參考文獻 173
第6章 動態(tài)規(guī)劃 174
6.1 動態(tài)規(guī)劃的思想方法 174
6.1.1 動態(tài)規(guī)劃的最優(yōu)決策原理 174
6.1.2 動態(tài)規(guī)劃實例——貨郎擔問題 175
6.2 多段圖的最短路徑問題 177
6.2.1 多段圖的決策過程 178
6.2.2 多段圖動態(tài)規(guī)劃算法的實現(xiàn) 180
6.3 資源分配問題 181
6.3.1 資源分配的決策過程 182
6.3.2 資源分配算法的實現(xiàn) 184
6.4 設備更新問題 187
6.4.1 設備更新問題的決策過程 187
6.4.2 設備更新算法的實現(xiàn) 190
6.5 最長公共子序列問題 192
6.5.1 最長公共子序列的搜索過程 192
6.5.2 最長公共子序列算法的實現(xiàn) 195
6.6 0/1背包問題 196
6.6.1 0/1背包問題的求解過程 196
6.6.2 0/1背包問題的實現(xiàn) 198
6.7 RNA最大堿基對匹配問題 199
6.7.1 RNA最大堿基對匹配的搜索過程 200
6.7.2 RNA最大堿基對匹配算法的實現(xiàn) 203
習題 205
參考文獻 207
第7章 回溯 208
7.1 回溯法的思想方法 208
7.1.1 問題的解空間和狀態(tài)空間樹 208
7.1.2 狀態(tài)空間樹的動態(tài)搜索 209
7.1.3 回溯法的一般性描述 211
7.2 n皇后問題 213
7.2.1 n皇后問題的求解過程 213
7.2.2 n皇后問題算法的實現(xiàn) 215
7.3 圖的著色問題 217
7.3.1 圖著色問題的求解過程 218
7.3.2 圖的m著色問題算法的實現(xiàn) 220
7.4 哈密爾頓回路問題 222
7.4.1 哈密爾頓回路的求解過程 222
7.4.2 哈密爾頓回路算法的實現(xiàn) 224
7.5 0/1背包問題 225
7.5.1 回溯法解0/1背包問題的求解過程 226
7.5.2 回溯法解0/1背包問題算法的實現(xiàn) 229
7.6 回溯法的效率分析 231
習題 234
參考文獻 235
第8章 分支與限界 236
8.1 分支與限界法的基本思想 236
8.2 作業(yè)分配問題 238
8.2.1 分支限界法解作業(yè)分配問題的思想方法 238
8.2.2 分支限界法解作業(yè)分配問題算法的實現(xiàn) 241
8.3 單源最短路徑問題 244
8.3.1 分支限界法解單源最短路徑問題的思想方法 244
8.3.2 分支限界法解單源最短路徑問題算法的實現(xiàn) 246
8.4 0/1背包問題 248
8.4.1 分支限界法解0/1背包問題的思想方法和求解過程 249
8.4.2 0/1背包問題分支限界算法的實現(xiàn) 251
8.5 貨郎擔問題 254
8.5.1 費用矩陣的特性及歸約 254
8.5.2 界限的確定和分支的選擇 256
8.5.3 貨郎擔問題的求解過程 259
8.5.4 幾個輔助函數(shù)的實現(xiàn) 262
8.5.5 貨郎擔問題分支限界算法的實現(xiàn) 268
習題 271
參考文獻 272
第9章 隨機算法 273
9.1 隨機算法概述 273
9.1.1 隨機算法的類型 273
9.1.2 隨機數(shù)發(fā)生器 274
9.2 舍伍德算法 275
9.2.1 隨機快速排序算法 275
9.2.2 隨機選擇算法 277
9.3 拉斯維加斯算法 280
9.3.1 字符串匹配 280
9.3.2 整數(shù)因子 284
9.4 蒙特卡羅算法 285
9.4.1 數(shù)組的主元素問題 285
9.4.2 素數(shù)測試 287
習題 290
參考文獻 291
第3篇 計算機應用領域的一些基法
第10章 圖和網(wǎng)絡問題 294
10.1 圖的遍歷 294
10.1.1 圖的深度優(yōu)先搜索遍歷 294
10.1.2 圖的廣度優(yōu)先搜索遍歷 299
10.1.3 無向圖的接合點 301
10.1.4 有向圖的強連通分支 305
10.2 網(wǎng)絡流 308
10.2.1 網(wǎng)絡流的概念 308
10.2.2 Ford_Fulkerson方法和最大容量增廣 312
10.2.3 最短路徑增廣 315
10.3 二分圖的最大匹配問題 320
10.3.1 預備知識 321
10.3.2 二分圖最大匹配的匈牙利樹方法 323
習題 329
參考文獻 331
第11章 計算幾何問題 332
11.1 引言 332
11.2 平面線段的交點問題 334
11.2.1 尋找平面線段交點的思想方法 335
11.2.2 尋找平面線段交點的實現(xiàn) 337
11.3 凸殼問題 342
11.3.1 凸殼問題的格雷厄姆掃描法 343
11.3.2 格雷厄姆掃描法的實現(xiàn) 344
11.4 平面點集的直徑問題 346
11.4.1 求取平面點集直徑的思想方法 346
11.4.2 平面點集直徑的求取 348
習題 350
參考文獻 351
第4篇 算法設計與分析的一些理論問題
第12章 NP完全問題 354
12.1 P類和NP類問題 355
12.1.1 P類問題 355
12.1.2 NP類問題 356
12.2 NP完全問題 358
12.2.1 NP完全問題的定義 358
12.2.2 幾個典型的NP完全問題 360
12.2.3 其他NP完全問題 366
12.3 co_NP類和NPI類問題 366
習題 369
參考文獻 370
第13章 計算復雜性 371
13.1 計算模型 371
13.1.1 圖靈機的基本模型 371
13.1.2 k帶圖靈機和時間復雜性 374
13.1.3 離線圖靈機和空間復雜性 376
13.1.4 可滿足性問題和Cook定理 379
13.2 復雜性類型之間的關系 381
13.2.1 時間復雜性和空間復雜性的關系 382
13.2.2 時間譜系定理和空間譜系定理 384
13.2.3 填充變元 389
13.3 歸約性關系 391
13.4 完備性 394
13.4.1 NLOGSPACE完全問題 394
13.4.2 PSPACE完全問題和P完全問題 396
習題 397
參考文獻 398
第14章 下界 399
14.1 平凡下界 399
14.2 判定樹模型 399
14.2.1 檢索問題 400
14.2.2 排序問題 401
14.3 代數(shù)判定樹模型 402
14.3.1 代數(shù)判定樹模型及下界定理 402
14.3.2 極點問題 404
14.4 線性時間歸約 405
14.4.1 凸殼問題 406
14.4.2 多項式插值問題 406
習題 408
參考文獻 408
第15章 近似算法 409
15.1 近似算法的性能 409
15.2 裝箱問題 410
15.2.1 首次適宜算法 411
15.2.2 最適宜算法及其他算法 412
15.3 頂點覆蓋問題 414
15.4 貨郎擔問題 416
15.4.1 歐幾里得貨郎擔問題 417
15.4.2 一般的貨郎擔問題 419
15.5 多項式近似方案 419
15.5.1 0/1背包問題的多項式近似方案 420
15.5.2 子集求和問題的完全多項式近似方案 423
習題 425
參考文獻 426
參考文獻 427
書單推薦
