定 價(jià)：59 元
叢書名：高等學(xué)校計(jì)算機(jī)專業(yè)系列教材
- 作者：黃宇
- 出版時(shí)間：2020/7/1
- ISBN：9787111657231
- 出 版 社：機(jī)械工業(yè)出版社
- 中圖法分類：TP301.6
- 頁碼：0
- 紙張：
- 版次：
- 開本：16開
本書是作者在多年從事算法設(shè)計(jì)與分析課程教學(xué)和研究的基礎(chǔ)上編寫而成，系統(tǒng)地介紹了算法設(shè)計(jì)與分析的理論、方法和技術(shù)。內(nèi)容圍繞兩條主線來組織。一條主線是介紹典范性的算法問題，如排序、選擇、圖遍歷等。 另一條主線是介紹典范性的算法設(shè)計(jì)分析策略，如分治、貪心、動(dòng)態(tài)規(guī)劃等算法設(shè)計(jì)策略和對(duì)手分析、平攤分析等算法分析策略。本書中兩條主線交替進(jìn)行，每條主線又各自分為基本和進(jìn)階兩部分。
前言
教學(xué)建議
第一部分計(jì)算模型
第1 章抽象的算法設(shè)計(jì)與分析........... 2
1.1 RAM 模型的引入................... 2
1.1.1 計(jì)算的基本概念................... 2
1.1.2計(jì)算模型的基本概念. . . . . . . .. .. . . . . 3
1.1.3RAM 模型........................ 3
1.1.4計(jì)算模型的選擇：易用性與精確性........................... 5
1.2 抽象算法設(shè)計(jì)...................... 6
1.2.1 算法問題規(guī)約..................... 6
1.2.2 算法正確性證明：數(shù)學(xué)歸納法....... 7
1.3 抽象算法分析...................... 8
1.3.1 抽象算法的性能指標(biāo). . . . . . . .. .. . . . . 8
1.3.2 最壞情況時(shí)間復(fù)雜度分析.......... 9
1.3.3 平均情況時(shí)間復(fù)雜度分析......... 10
1.4 習(xí)題. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 11
第2 章從算法的視角重新審視數(shù)學(xué)的概念. . . . . . . . . . .. .. .. .. . . . . 14
2.1 數(shù)學(xué)運(yùn)算背后的算法操作......... 14
2.1.1 取整. x . 和. x . . . . . . . . . . .. .. .. .. . 14
2.1.2 對(duì)數(shù)log n . . . . .. .. .. . . . . . . . . . .. .. . 14
2.1.3 階乘n!. . . . .. .. .. .. . . . . . . . . . .. .. . 15
2.1.4 常用級(jí)數(shù)求和.f (i). . . . . . .. .. .. .. 16
2.1.5 期望E[X] ....................... 18
2.2 函數(shù)的漸近增長(zhǎng)率................ 19
2.3 “分治遞歸”求解................. 21
2.3.1 替換法. .. .. . . . . . . . . . .. .. .. .. . . . . 21
2.3.2 分治遞歸與遞歸樹.. . . . . . . . . . .. .. .21
2.3.3 Master 定理. .. .. .. . . . . . . . . . .. .. .. 22
2.4 習(xí)題. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 23
第二部分從蠻力到分治
第3 章蠻力算法設(shè)計(jì)................... 31
3.1 蠻力選擇與查找. . . . . . .. .. .. . . . . . . . 31
3.2 蠻力排序.. . . . . . .. .. .. .. . . . . . . . . . .. 32
3.2.1選擇排序. . . .. .. .. .. . . . . . . . . . .. .. 32
3.2.2插入排序. . . .. .. .. .. . . . . . . . . . .. .. 33
3.3 習(xí)題. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 35
第4 章分治排序.. .. .. .. . . . . . .. .. .. .. . . . 37
4.1 快速排序. . . . . . . .. .. .. .. . . . . . . . . . .. 37
4.1.1插入排序的不足. .. .. . . . . . . . . . .. .. 37
4.1.2快速排序的改進(jìn). .. .. . . . . . . . . . .. .. 38
4.1.3最壞情況時(shí)間復(fù)雜度分析......... 39
4.1.4基于遞歸方程的平均情況時(shí)間復(fù)雜度分析. . . . . . .. .. .. . . . . . . . . . . 40
4.1.5基于指標(biāo)隨機(jī)變量的平均情況時(shí)間復(fù)雜度分析. . . . . . .. .. .. . . . . . . . . . . 41
4.2 合并排序.. . . . . . .. .. .. .. . . . . . . . . . .. 43
4.3 基于比較的排序的下界. .. .. .. . . . . . 44
4.3.1決策樹的引入. . . . . . .. .. .. . . . . . . . . 45
4.3.2比較排序的最壞情況時(shí)間復(fù)雜度的下界. . . . . .. .. .. .. . . . . . . . .. .. .. 45
4.3.3比較排序的平均情況時(shí)間復(fù)雜度的下界. . . . . .. .. .. .. . . . . . . . .. .. .. 46
4.4 習(xí)題. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 48
第5 章線性時(shí)間選擇................... 50
5.1 期望線性時(shí)間選擇................ 50
5.1.1選擇算法設(shè)計(jì). . . . . . .. .. .. . . . . . . . . 50
5.1.2選擇算法分析. . . . . . .. .. .. . . . . . . . . 51
5.2 最壞情況線性時(shí)間選擇. .. .. .. . . . . . 52
5.2.1選擇算法設(shè)計(jì). . . . . . .. .. .. . . . . . . . . 52
5.2.2選擇算法分析. .. . . . . . . . . . .. .. . . . . 53
5.3 習(xí)題. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 54
第6 章對(duì)數(shù)時(shí)間查找................... 57
6.1 折半查找.. .. . . . . . . . .. .. .. .. . . . . . . . 57
6.1.1經(jīng)典折半查找. .. . . . . . . . .. .. .. . . . . 57
6.1.2查找峰值. . . . . . . .. .. .. . . . . . . . . . .. 58
6.1.3計(jì)算√N(yùn) ........................ 59
6.2 平衡二叉搜索樹. . . . . . . . .. .. .. . . . . . 59
6.2.1二叉搜索樹及其平衡性........... 59
6.2.2紅黑樹的定義. .. . . . . . . . . . .. .. . . . . 60
6.2.3紅黑樹的平衡性. .. .. .. .. . . . . . . . . . 62
6.3 習(xí)題. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 62
第7 章分治算法設(shè)計(jì)要素. . . . . . . . . . .. .. .65
7.1 分治算法的關(guān)鍵特征. . . . . . . .. .. .. . 65
7.2 計(jì)算逆序?qū)Φ膫�(gè)數(shù)................ 66
7.2.1依托于合并排序的逆序?qū)τ?jì)數(shù).. .. . 66
7.2.2原地的逆序?qū)τ?jì)數(shù).. .. . . . . . . . . . .. .67
7.3 整數(shù)乘法.. .. . . . . . . . .. .. .. .. . . . . . . . 68
7.3.1簡(jiǎn)單分治. . . . . . . .. .. .. . . . . . . . . . .. 69
7.3.2更精細(xì)的分治. .. . . . . . .. .. .. .. . . . . 69
7.4 芯片檢測(cè).. .. . . . . . . . .. .. .. .. . . . . . . . 70
7.5 習(xí)題. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 71
第三部分從圖遍歷到圖優(yōu)化
第8 章圖的深度優(yōu)先遍歷. . . . . . . . . . .. .. .76
8.1 圖和圖遍歷. . . . . . . .. .. .. .. . . . . . . . . . 76
8.2 有向圖上的深度優(yōu)先遍歷......... 77
8.2.1遍歷框架. . . . . . . .. .. .. . . . . . . . . . .. 77
8.2.2深度優(yōu)先遍歷樹. .. .. .. .. . . . . . . . . . 79
8.2.3活動(dòng)區(qū)間. . . . . . . .. .. .. . . . . . . . . . .. 79
8.3 有向圖上深度優(yōu)先遍歷的應(yīng)用.. .. .82
8.3.1拓?fù)渑判? . . . . . . .. .. .. . . . . . . . . . .. 82
8.3.2關(guān)鍵路徑. . . . . . . .. .. .. . . . . . . . . . .. 85
8.3.3有向圖中的強(qiáng)連通片............. 87
8.4 無向圖上的深度優(yōu)先遍歷......... 91
8.4.1無向圖的深度優(yōu)先遍歷樹......... 91
8.4.2無向圖的深度優(yōu)先遍歷框架....... 92
8.5 無向圖上深度優(yōu)先遍歷的應(yīng)用.. .. .93
8.5.1容錯(cuò)連通. . . .. .. .. .. . . . . . . . . . .. .. 93
8.5.2尋找割點(diǎn). . . .. .. .. .. . . . . . . . . . .. .. 94
8.5.3尋找橋. . . . . . . . . . .. .. .. .. . . . . . . . . 96
8.6 習(xí)題. . . . . . . . . . .. .. .. . . . . . . . .. .. .. .. 97
第9 章圖的廣度優(yōu)先遍歷............. 102
9.1 廣度優(yōu)先遍歷. . . . . . . .. .. .. .. . . . . . 102
9.1.1廣度優(yōu)先遍歷框架.............. 103
9.1.2有向圖的廣度優(yōu)先遍歷樹. . . . . . . . 105
9.1.3無向圖的廣度優(yōu)先遍歷樹. . . . . . . . 106
9.2 廣度優(yōu)先遍歷的應(yīng)用. . . . .. .. .. . . . 107
9.2.1判斷二分圖. .. . . . . . . . . . .. .. .. .. . 107
9.2.2尋找k 度子圖.. .. .. . . . . . . . .. .. .. 108
9.3 習(xí)題. . . . . . . . . .. .. .. . . . . . . . . . .. .. .. 109
第10 章圖優(yōu)化問題的貪心求解. . . . . . ..111
10.1最小生成樹問題與給定源點(diǎn)最短路徑問題. . . . .. .. .. . . . . . . . . . 111
10.2Prim 算法. .. . . . . . . . .. .. .. . . . . . . . .112
10.2.1Prim 算法的正確性. .. . . . . . . . . . . 113
10.2.2Prim 算法的實(shí)現(xiàn). . . . . . .. .. .. . . . 116
10.2.3Prim 算法的分析. . . . . . .. .. .. . . . 117
10.3Kruskal 算法. . . . . . . . . .. .. .. .. . . . . 118
10.3.1Kruskal 算法的正確性. . . . . . . . . . .119
10.3.2Kruskal 算法的實(shí)現(xiàn)與分析...... 120
10.4最小生成樹貪心構(gòu)建框架MCE. . . . . . . . . . .. .. .. . . . . . . . . . .. ..120
10.4.1從MCE 框架的角度分析Prim 算法..................... 121
10.4.2從MCE 框架的角度分析Kruskal 算法. .. . . . . . . . . . .. .. .. . 122
10.5Dijkstra 算法. .. .. . . . . . . . . . .. .. .. . 123
10.5.1Dijkstra 算法的設(shè)計(jì).. . . . . . . . . . ..123
10.5.2Dijkstra 算法的正確性證明與性能分析. .. . . . . . . . . . .. .. .. .. . . 125
10.6貪心遍歷框架BestFS. .. .. .. . . . . . 126
10.7 習(xí)題. . . . . . . . . .. .. . . . . . . . . . .. .. .. .128
第11 章貪心算法設(shè)計(jì)要素............ 134
11.1貪心算法的基本結(jié)構(gòu). . .. .. .. .. . . 134
11.2相容任務(wù)調(diào)度問題.............. 134
11.2.1直覺的嘗試. . . .. .. .. . . . . . . . . . .. 135
11.2.2基于任務(wù)結(jié)束時(shí)間的貪心算法. . . 135
11.3Hu.man 編碼.. .. .. . . . . . . . .. .. .. . 136
11.3.1可變長(zhǎng)度編碼.. . . . . . . . . . .. .. .. .136
11.3.2最優(yōu)編碼方案的性質(zhì)........... 137
11.3.3貪心的Hu.man 編碼........... 139
11.4 習(xí)題.. .. . . . . . . . .. .. .. . . . . . . . . . .. .139
第12 章圖優(yōu)化問題的動(dòng)態(tài)規(guī)劃求解. . . 142
12.1有向無環(huán)圖上的給定源點(diǎn)最短路徑問題. . . . . . . . .. .. . . . . . . . 142
12.2所有點(diǎn)對(duì)最短路徑問題......... 143
12.2.1傳遞閉包問題和Shortcut 算法... 143
12.2.2所有點(diǎn)對(duì)最短路徑：基于路徑長(zhǎng)度的遞歸........... 145
12.2.3Floyd-Warshall 算法：基于中繼節(jié)點(diǎn)范圍的遞歸. . . . . . . 146
12.3 習(xí)題.. .. . . . . . . . . . .. .. . . . . . . . . . .. .147
第13 章動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)要素. . . . . . . .150
13.1動(dòng)態(tài)規(guī)劃的動(dòng)機(jī). . . . . . . .. .. .. . . . . 150
13.2動(dòng)態(tài)規(guī)劃的引入. . . . . . . .. .. .. . . . . 151
13.2.1基于樸素遍歷的遞歸........... 152
13.2.2未做規(guī)劃的遞歸............... 152
13.2.3采用動(dòng)態(tài)規(guī)劃的遞歸........... 153
13.3動(dòng)態(tài)規(guī)劃的關(guān)鍵特征. . . . . . .. .. .. 155
13.4動(dòng)態(tài)規(guī)劃應(yīng)用舉例.............. 156
13.4.1編輯距離問題.. . . . . . . . . . .. .. .. .156
13.4.2硬幣兌換問題.. . . . . . . . . . .. .. .. .158
13.4.3最大和連續(xù)子序列問題......... 159
13.4.4相容任務(wù)調(diào)度問題............. 160
13.5習(xí)題.. .. . . . . . .. .. .. .. . . . . . . . . . .. .161
第四部分圍繞數(shù)據(jù)結(jié)構(gòu)的算法設(shè)計(jì)
第14 章堆與偏序關(guān)系.. .. .. .. . . . . . . . . . 168
14.1堆的定義. .. . . . . . . . .. .. .. .. . . . . . . 168
14.2堆的抽象維護(hù).. . . . . . . . . . .. .. .. . . 168
14.2.1堆的修復(fù). . . . . . . . .. .. .. .. . . . . . . 169
14.2.2堆的構(gòu)建. . . . .. .. .. .. . . . . . . . . . . 169
14.3堆的具體實(shí)現(xiàn). . . . . . . . . .. .. .. . . . . 171
14.4堆的應(yīng)用. . . . . . .. .. .. .. . . . . . . . . . . 172
14.4.1堆排序.. .. .. . . . . . . . . . .. .. . . . . . 172
14.4.2基于堆實(shí)現(xiàn)優(yōu)先隊(duì)列........... 173
14.5 習(xí)題. . . . . . . .. .. .. . . . . . . . . . .. .. .. .174
第15 章并查集與動(dòng)態(tài)等價(jià)關(guān)系. . . . . . ..176
15.1動(dòng)態(tài)等價(jià)關(guān)系. . . . . . . . . .. .. . . . . . . 176
15.2基于根樹的基礎(chǔ)實(shí)現(xiàn)：普通“并”+普通“查”. .. .. .. . . .177
15.3保證合并的平衡性：加權(quán)“并”+普通“查”. .. .. .. . . .178
15.4降低查找的代價(jià)：加權(quán)“并”+路徑壓縮“查”.. .. . 179
15.5 習(xí)題. . . . . . . . . .. .. . . . . . . . . . .. .. .. .180
第16 章哈希表與查找.. .. . . . . . . . . . .. .. 182
16.1直接尋址表：查找表的蠻力實(shí)現(xiàn). .. .. . . . . . . . . . .. .. .. ..182
16.2哈希表的基本原理.............. 183
16.3封閉尋址沖突消解.............. 183
16.4開放尋址沖突消解.............. 185
16.5 習(xí)題. . . . . . . . . .. .. . . . . . . . . . .. .. .. .188
第17 章有限自動(dòng)機(jī)與串匹配. .. . . . . . . . 189
17.1蠻力串匹配..................... 189
17.2基于有限自動(dòng)機(jī)的串匹配. . . . . .. 190
17.3從有限自動(dòng)機(jī)的角度理解KMP 算法....................... 191
17.3.1對(duì)傳統(tǒng)匹配自動(dòng)機(jī)的改進(jìn).. . . . . . 191
17.3.2自動(dòng)機(jī)構(gòu)建的原理............. 192
17.3.3KMP 算法的實(shí)現(xiàn).. .. . . . . . .. .. .. 193
17.4習(xí)題. . . . . . . . . .. .. . . . . . . . . . .. .. .. .194
第五部分算法分析進(jìn)階
第18 章平攤分析. .. . . . . . . . . . .. .. .. .. . . 198
18.1平攤分析的動(dòng)機(jī). . . .. .. .. .. . . . . . . 198
18.2平攤分析的基本過程. . .. .. .. .. . . 199
18.3MultiPop 棧. . . . . . . . .. .. .. . . . . . . . . 200
18.4 數(shù)組擴(kuò)充. . . . . . . . . . .. .. .. .. . . . . . . 201
18.5 二進(jìn)制計(jì)數(shù)器.. . . . . . . . . . .. .. .. . . 202
18.6 基于棧實(shí)現(xiàn)隊(duì)列. . . . . . . .. .. .. . . . . 203
18.7 習(xí)題.. .. . . . . . . . . . .. .. . . . . . . . . . .. .204
第19 章對(duì)手論證. .. .. .. . . . . . . . . . .. .. .. 207
19.1 對(duì)手論證的基本形式. . . . . . . . .. .. 207
19.2 選擇最大或最小元素. . . . . . .. .. .. 207
19.3 同時(shí)選擇最大和最小元素. . . . . . . 208
19.4 選擇次大元素.. . . . . . . . . . .. .. .. . . 209
19.5 選擇中位數(shù)..................... 211
19.6 習(xí)題.. .. . . . . . . . .. .. .. . . . . . . . . . .. .212
第六部分計(jì)算復(fù)雜性初步
第20 章問題與歸約................... 216
20.1 NP 問題. . . . . . . . . . .. .. .. .. . . . . . . . 216
20.1.1 優(yōu)化問題和判定問題........... 216
20.1.2 P 問題的定義. . . . . . . . . .. .. .. .. . 216
20.1.3 NP 問題的定義. .. .. .. .. . . . . . . . .217
20.2 問題間的歸約. . . . . . . .. .. .. . . . . . . 218
20.2.1 歸約的定義. .. .. . . . . . . . . . .. .. .. 218
20.2.2 歸約的代價(jià)與問題難度的比較. .. 219
20.3 習(xí)題. . . . . . . .. .. .. . . . . . . . . . .. .. .. .219
第21 章NP 完全性理論初步.. .. .. .. . . . 221
21.1 NP 完全問題的定義. . . . .. .. .. . . . 221
21.2 NP 完全性證明的初步知識(shí). . . .. . 222
21.2.1 一般問題和特例問題........... 222
21.2.2 等價(jià)問題. . . . .. .. .. .. . . . . . . . . . . 223
21.3 習(xí)題. . . . . . . .. .. .. . . . . . . . . . .. .. .. .224
附錄A 數(shù)學(xué)歸納法. .. .. . . . . . . . . . .. .. .. . 226
附錄B 二叉樹. . . . . . . . .. .. .. . . . . . . . . . .. .227
參考文獻(xiàn)................................ 228
書單推薦
