第1部分 算法和算法分析
第1章 算法問(wèn)題求解基礎(chǔ) 1
1.1 算法概述 1
1.1.1 什么是算法 1
1.1.2 為什么學(xué)習(xí)算法 3
1.2 問(wèn)題求解方法 3
1.2.1 問(wèn)題和問(wèn)題求解 4
1.2.2 問(wèn)題求解過(guò)程 4
1.2.3 軟件生命周期 5
1.3 算法設(shè)計(jì)與分析 5
1.3.1 算法問(wèn)題求解過(guò)程 5
1.3.2 如何設(shè)計(jì)算法 6
1.3.3 如何表示算法 6
1.3.4 如何確認(rèn)算法 6
1.3.5 如何分析算法 7
1.4 遞歸和歸納 7
1.4.1 遞歸 7
1.4.2 遞歸算法示例 9
1.4.3 歸納證明 11
習(xí)題1 13
第2章 算法分析基礎(chǔ) 14
2.1 算法復(fù)雜度 14
2.1.1 什么是好的算法 14
2.1.2 影響程序執(zhí)行時(shí)間的因素 15
2.1.3 算法的時(shí)間復(fù)雜度 16
2.1.4 使用程序步分析算法 17
2.1.5 算法的空間復(fù)雜度 18
2.2 漸近表示法 19
2.2.1 大O記號(hào) 19
2.2.2 Ω記號(hào) 20
2.2.3 Θ記號(hào) 21
2.2.4 小o記號(hào) 21
2.2.5 算法按時(shí)間復(fù)雜度分類(lèi) 21
2.3 遞推關(guān)系 22
2.3.1 遞推方程 22
2.3.2 替換方法 23
2.3.3 迭代方法 23
2.3.4 遞歸樹(shù) 23
2.3.5 主方法 25
2.4 分?jǐn)偡治?25
2.4.1 聚集分析 26
2.4.2 會(huì)計(jì)方法 26
2.4.3 勢(shì)能方法 27
習(xí)題2 28
第3章 伸展樹(shù)與跳表 31
3.1 伸展樹(shù) 31
3.1.1 二叉搜索樹(shù) 31
3.1.2 自調(diào)節(jié)樹(shù)和伸展樹(shù) 31
3.1.3 伸展操作 32
3.1.4 伸展樹(shù)類(lèi) 34
3.1.5 旋轉(zhuǎn)的實(shí)現(xiàn) 34
3.1.6 插入運(yùn)算的實(shí)現(xiàn) 35
3.1.7 分?jǐn)偡治?37
3.2 跳表 39
3.2.1 什么是跳表 39
3.2.2 跳表類(lèi) 40
3.2.3 層次分配 42
3.2.4 插入運(yùn)算的實(shí)現(xiàn) 43
3.2.5 性能分析 44
習(xí)題3 45

第2部分 算法設(shè)計(jì)策略

第4章 基本搜索和遍歷方法 46
4.1 基本概念 46
4.2 圖的搜索和遍歷 47
4.2.1 搜索方法 47
4.2.2 鄰接表類(lèi) 48
4.2.3 廣度優(yōu)先搜索 49
4.2.4 深度優(yōu)先搜索 51
4.3 雙連通分量 53
4.3.1 基本概念 53
4.3.2 發(fā)現(xiàn)關(guān)節(jié)點(diǎn) 54
4.3.3 構(gòu)造雙連通圖 58
4.4 與或圖 58
4.4.1 問(wèn)題分解 58
4.4.2 判斷與或樹(shù)是否可解 60
4.4.3 構(gòu)建解樹(shù) 61
4.5 區(qū)間最值查詢(xún)（RMQ） 62
4.5.1 區(qū)間信息維護(hù)與查詢(xún) 62
4.5.2 ST算法求解RMQ問(wèn)題 63
4.6 最近公共祖先（LCA） 65
4.6.1 概述 65
4.6.2 倍增法求解LCA問(wèn)題 66
4.6.3 在線RMQ法求解LCA問(wèn)題 68
4.6.4 Tarjan算法求解LCA問(wèn)題 70
習(xí)題4 73
第5章 分治法 75
5.1 一般方法 75
5.1.1 分治法的基本思想 75
5.1.2 算法分析 76
5.1.3 數(shù)據(jù)結(jié)構(gòu) 77
5.2 求最大、最小元 78
5.2.1 分治法求解 78
5.2.2 時(shí)間分析 79
5.3 二分搜索 80
5.3.1 分治法求解 80
5.3.2 對(duì)半搜索 81
5.3.3 二叉判定樹(shù) 82
5.3.4 搜索算法的時(shí)間下界 84
5.4 排序問(wèn)題 85
5.4.1 合并排序 85
5.4.2 快速排序 87
5.4.3 排序算法的時(shí)間下界 91
5.5 選擇問(wèn)題 92
5.5.1 分治法求解 92
5.5.2 隨機(jī)選擇主元 93
5.5.3 線性時(shí)間選擇算法 94
5.5.4 時(shí)間分析 96
5.5.5 允許重復(fù)元素的選擇算法 97
5.6 斯特拉森矩陣乘法 97
5.6.1 分治法求解 97
5.6.2 斯特拉森矩陣乘法簡(jiǎn)介 98
習(xí)題5 99
第6章 貪心法 102
6.1 一般方法 102
6.2 背包問(wèn)題 103
6.2.1 問(wèn)題描述 103
6.2.2 貪心法求解 104
6.2.3 算法正確性 105
6.3 帶時(shí)限的作業(yè)排序問(wèn)題 106
6.3.1 問(wèn)題描述 106
6.3.2 貪心法求解 107
6.3.3 算法正確性 108
6.3.4 可行性判定 108
6.3.5 作業(yè)排序貪心算法 109
6.3.6 改進(jìn)算法 110
6.4 最佳合并模式 112
6.4.1 問(wèn)題描述 113
6.4.2 貪心法求解 113
6.4.3 算法正確性 115
6.5 最小代價(jià)生成樹(shù) 116
6.5.1 問(wèn)題描述 116
6.5.2 貪心法求解 116
6.5.3 普里姆算法 117
6.5.4 克魯斯卡爾算法 119
6.5.5 算法正確性 121
6.6 單源最短路徑 122
6.6.1 問(wèn)題描述 122
6.6.2 貪心法求解 122
6.6.3 迪杰斯特拉算法 123
6.6.4 算法正確性 125
6.7 磁帶最優(yōu)存儲(chǔ) 127
6.7.1 單帶最優(yōu)存儲(chǔ) 127
6.7.2 多帶最優(yōu)存儲(chǔ) 128
6.8 貪心法的基本要素 129
6.8.1 最優(yōu)量度標(biāo)準(zhǔn) 129
6.8.2 最優(yōu)子結(jié)構(gòu) 129
習(xí)題6 130
第7章 動(dòng)態(tài)規(guī)劃法 133
7.1 一般方法和基本要素 133
7.1.1 一般方法 133
7.1.2 基本要素 134
7.1.3 多段圖問(wèn)題 134
7.1.4 資源分配問(wèn)題 137
7.1.5 關(guān)鍵路徑問(wèn)題 138
7.2 每對(duì)結(jié)點(diǎn)間的最短路徑 140
7.2.1 問(wèn)題描述 140
7.2.2 動(dòng)態(tài)規(guī)劃法求解 140
7.2.3 弗洛伊德算法 141
7.2.4 算法正確性 143
7.3 矩陣連乘 143
7.3.1 問(wèn)題描述 143
7.3.2 動(dòng)態(tài)規(guī)劃法求解 144
7.3.3 矩陣連乘算法 145
7.3.4 備忘錄方法 147
7.4 最長(zhǎng)公共子序列 147
7.4.1 問(wèn)題描述 147
7.4.2 動(dòng)態(tài)規(guī)劃法求解 148
7.4.3 最長(zhǎng)公共子序列算法 149
7.4.4 改進(jìn)算法 151
7.5 最優(yōu)二叉搜索樹(shù) 151
7.5.1 問(wèn)題描述 151
7.5.2 動(dòng)態(tài)規(guī)劃法求解 151
7.5.3 最優(yōu)二叉搜索樹(shù)算法 153
7.6 0/1背包問(wèn)題 155
7.6.1 問(wèn)題描述 155
7.6.2 動(dòng)態(tài)規(guī)劃法求解 155
7.6.3 0/1背包問(wèn)題算法框架 157
7.6.4 0/1背包問(wèn)題算法 160
7.6.5 性能分析 162
7.6.6 使用啟發(fā)式方法 163
7.7 流水線作業(yè)調(diào)度 164
7.7.1 問(wèn)題描述 164
7.7.2 動(dòng)態(tài)規(guī)劃法求解 165
7.7.3 Johnson算法 167
習(xí)題7 168
第8章 回溯法 170
8.1 一般方法 170
8.1.1 基本概念 170
8.1.2 剪枝函數(shù)和回溯法 171
8.1.3 回溯法的效率分析 173
8.2 n-皇后問(wèn)題 173
8.2.1 問(wèn)題描述 173
8.2.2 回溯法求解 174
8.2.3 n-皇后算法 175
8.2.4 時(shí)間分析 176
8.3 子集和數(shù)問(wèn)題 177
8.3.1 問(wèn)題描述 177
8.3.2 回溯法求解 177
8.3.3 子集和數(shù)算法 178
8.4 圖著色問(wèn)題 180
8.4.1 問(wèn)題描述 180
8.4.2 回溯法求解 180
8.4.3 圖著色算法 181
8.4.4 時(shí)間分析 182
8.5 哈密頓環(huán)問(wèn)題 182
8.5.1 問(wèn)題描述 182
8.5.2 哈密頓環(huán)算法 183
8.6 0/1背包問(wèn)題 184
8.6.1 問(wèn)題描述 184
8.6.2 回溯法求解 184
8.6.3 限界函數(shù) 185
8.6.4 0/1背包問(wèn)題算法 186
8.7 批處理作業(yè)調(diào)度 188
8.7.1 問(wèn)題描述 188
8.7.2 回溯法求解 188
8.7.3 批處理作業(yè)調(diào)度算法 188
習(xí)題8 190
第9章 分枝限界法 192
9.1 一般方法 192
9.1.1 分枝限界法概述 192
9.1.2 LC分枝限界法 194
9.1.3 15謎問(wèn)題 195
9.2 求最優(yōu)解的分枝限界法 197
9.2.1 上下界函數(shù) 197
9.2.2 FIFO分枝限界法 198
9.2.3 LC分枝限界法 199
9.3 帶時(shí)限的作業(yè)排序 200
9.3.1 問(wèn)題描述 200
9.3.2 分枝限界法求解 200
9.3.3 帶時(shí)限的作業(yè)排序算法 201
9.4 0/1背包問(wèn)題 203
9.4.1 問(wèn)題描述 203
9.4.2 分枝限界法求解 203
9.4.3 0/1背包問(wèn)題算法 204
9.5 旅行商問(wèn)題 207
9.5.1 問(wèn)題描述 207
9.5.2 分枝限界法求解 207
9.6 批處理作業(yè)調(diào)度 211
9.6.1 問(wèn)題描述 211
9.6.2 分枝限界法求解 211
9.6.3 批處理作業(yè)調(diào)度算法 212
習(xí)題9 215

第3部分 求解困難問(wèn)題

第10章 NP完全問(wèn)題 217
10.1 基本概念 217
10.1.1 不確定算法和不確定機(jī) 218
10.1.2 可滿足性問(wèn)題 220
10.1.3 P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題 221
10.1.4 NP難度問(wèn)題和NP完全問(wèn)題 221
10.2 Cook定理和證明 222
10.2.1 Cook定理 222
10.2.2 簡(jiǎn)化的不確定機(jī)模型 222
10.2.3 證明Cook定理 223
10.3 一些典型的NP完全問(wèn)題 227
10.3.1 最大集團(tuán) 227
10.3.2 頂點(diǎn)覆蓋 228
10.3.3 三元CNF可滿足性 229
10.3.4 圖的著色數(shù) 230
10.3.5 有向哈密頓環(huán) 231
10.3.6 恰切覆蓋 233
10.3.7 子集和數(shù) 234
10.3.8 分劃 235
習(xí)題10 236
第11章 隨機(jī)算法 238
11.1 基本概念 238
11.1.1 隨機(jī)算法概述 238
11.1.2 隨機(jī)數(shù)發(fā)生器 238
11.1.3 隨機(jī)算法分類(lèi) 239
11.2 拉斯維加斯算法 240
11.2.1 標(biāo)記重復(fù)元素算法 240
11.2.2 性能分析 241
11.2.3 n-皇后問(wèn)題 242
11.2.4 拉斯維加斯算法和回溯法的結(jié)合
算法 244
11.3 蒙特卡羅算法 245
11.3.1 多數(shù)元素問(wèn)題 246
11.3.2 素?cái)?shù)測(cè)試問(wèn)題 247
11.3.3 偽素?cái)?shù)測(cè)試問(wèn)題 248
11.3.4 米勒-拉賓算法 249
11.4 舍伍德算法 250
11.4.1 快速排序舍伍德算法 250
11.4.2 性能分析 251
11.4.3 舍伍德算法的其他應(yīng)用 251
習(xí)題11 252
第12章 近似算法 253
12.1 近似算法的性能 253
12.1.1 基本概念 253
12.1.2 絕對(duì)性能保證 253
12.1.3 相對(duì)性能保證 254
12.1.4 近似方案 255
12.2 絕對(duì)近似算法的應(yīng)用 255
12.2.1 最多程序存儲(chǔ)問(wèn)題 255
12.2.2 NP難度問(wèn)題 256
12.3 ?-近似算法的應(yīng)用 257
12.3.1 頂點(diǎn)覆蓋問(wèn)題 257
12.3.2 旅行商問(wèn)題 258
12.3.3 NP難度?-近似旅行商問(wèn)題 259
12.3.4 具有三角不等式性質(zhì)的旅行商
問(wèn)題 260
12.3.5 多機(jī)調(diào)度問(wèn)題 261
12.4 ?(n)-近似算法 263
12.4.1 集合覆蓋問(wèn)題 263
12.4.2 集合覆蓋問(wèn)題近似算法 264
12.4.3 ln(n)-近似算法 264
12.5 多項(xiàng)式時(shí)間近似方案 266
12.5.1 多機(jī)調(diào)度近似方案 266
12.5.2 時(shí)間分析 267
12.6 子集和數(shù)問(wèn)題的完全多項(xiàng)式時(shí)間近似
方案 267
12.6.1 子集和數(shù)問(wèn)題的指數(shù)時(shí)間算法 267
12.6.2 完全多項(xiàng)式時(shí)間近似方案 268
習(xí)題12 270
第13章 遺傳算法 272
13.1 進(jìn)化計(jì)算 272
13.2 遺傳算法的生物學(xué)基礎(chǔ) 273
13.3 遺傳算法的基本思想 274
13.4 基本遺傳算法 275
13.4.1 基本遺傳算法的構(gòu)成要素 275
13.4.2 基本遺傳算法的流程圖 278
13.5 遺傳算法的特點(diǎn)和應(yīng)用 278
13.5.1 遺傳算法的特點(diǎn) 278
13.5.2 遺傳算法的應(yīng)用 278
13.6 基本遺傳算法的實(shí)現(xiàn)方法 279
13.6.1 數(shù)據(jù)結(jié)構(gòu) 279
13.6.2 主程序 279
13.6.3 選擇運(yùn)算 280
13.6.4 交叉運(yùn)算 282
13.6.5 變異運(yùn)算 283
13.7 旅行商問(wèn)題 283
13.7.1 排列編碼 284
13.7.2 目標(biāo)函數(shù)和適應(yīng)度函數(shù) 284
13.7.3 錦標(biāo)賽選擇法 284
13.7.4 順序交叉 285
13.7.5 交換變異 286
13.7.6 參數(shù)選擇 287
13.7.7 實(shí)例運(yùn)行結(jié)果 287
習(xí)題13 288
第14章 密碼算法 289
14.1 信息安全和密碼學(xué) 289
14.1.1 信息安全 289
14.1.2 什么是密碼 289
14.1.3 密碼體制 290
14.2 數(shù)論初步 291
14.3 背包問(wèn)題密碼算法 292
14.3.1 背包問(wèn)題 292
14.3.2 超遞增背包問(wèn)題 293
14.3.3 由私人密鑰產(chǎn)生公開(kāi)密鑰 294
14.3.4 加密方法 294
14.3.5 解密方法 294
14.3.6 背包問(wèn)題安全性 295
14.4 RSA算法 295
14.4.1 RSA算法概述 295
14.4.2 RSA算法安全性 296
14.5 散列函數(shù)和消息認(rèn)證 297
14.5.1 散列函數(shù) 297
14.5.2 散列函數(shù)的結(jié)構(gòu) 297
14.5.3 消息認(rèn)證 298
14.6 數(shù)字簽名 298
14.6.1 RSA算法實(shí)現(xiàn)直接數(shù)字簽名 298
14.6.2 需仲裁的數(shù)字簽名 299
習(xí)題14 299
參考文獻(xiàn) 300