算法設(shè)計(jì)與分析 C++語言描述（第3版）

第1部分 算法和算法分析 

第1章 算法問題求解基礎(chǔ) 1

1．1 算法概述 1

1．1．1 什么是算法 1

1．1．2 為什么學(xué)習(xí)算法 3

1．2 問題求解方法 3

1．2．1 問題和問題求解 4

1．2．2 問題求解過程 4

1．2．3 系統(tǒng)生命周期 5

1．3 算法設(shè)計(jì)與分析 5

1．3．1 算法問題求解過程 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

本章小結(jié) 12

習(xí)題1 13

第2章 算法分析基礎(chǔ) 14

2．1 算法復(fù)雜度 14

2．1．1 什么是好的算法 14

2．1．2 影響程序運(yùn)行時(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ù)雜度分類 21

2．3 遞推關(guān)系 22

2．3．1 遞推方程 22

2．3．2 替換方法 23

2．3．3 迭代方法 23

2．3．4 主方法 24

2．4 分?jǐn)偡治?nbsp;25

2．4．1 聚集方法 26

2．4．2 會(huì)計(jì)方法 26

2．4．3 勢能方法 27

本章小結(jié) 28

習(xí)題2 28

第3章 伸展樹與跳表 30

3．1 伸展樹 30

3．1．1 二叉搜索樹 30

3．1．2 自調(diào)節(jié)樹和伸展樹 30

3．1．3 伸展操作 31

3．1．4 伸展樹類 32

3．1．5 旋轉(zhuǎn)的實(shí)現(xiàn) 34

3．1．6 插入運(yùn)算的實(shí)現(xiàn) 34

3．1．7 分?jǐn)偡治?nbsp;36

3．2 跳表 38

3．2．1 什么是跳表 38

3．2．2 跳表類 39

3．2．3 級數(shù)分配 41

3．2．4 插入運(yùn)算的實(shí)現(xiàn) 42

3．2．5 性能分析 43

本章小結(jié) 44

習(xí)題3 44

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

第4章 基本搜索和遍歷方法 45

4．1 基本概念 45

4．2 圖的搜索和遍歷 46

4．2．1 搜索方法 46

4．2．2 鄰接表類 47

4．2．3 廣度優(yōu)先搜索 48

4．2．4 深度優(yōu)先搜索 50

4．3 雙連通分量 53

4．3．1 基本概念 53

4．3．2 發(fā)現(xiàn)關(guān)節(jié)點(diǎn) 54

4．3．3 構(gòu)造雙連通圖 57

4．4 與或圖 58

4．4．1 問題分解 58

4．4．2 判斷與或樹是否可解 59

4．4．3 構(gòu)建解樹 61

本章小結(jié) 62

習(xí)題4 62

第5章 分治法 64

5．1 一般方法 64

5．1．1 分治法的基本思想 64

5．1．2 算法分析 65

5．1．3 數(shù)據(jù)結(jié)構(gòu) 66

5．2 求最大最小元 67

5．2．1 分治法求解 67

5．2．2 時(shí)間分析 68

5．3 二分搜索 69

5．3．1 分治法求解 69

5．3．2 對半搜索 70

5．3．3 二叉判定樹 71

5．3．4 搜索算法的時(shí)間下界 73

5．4 排序問題 74

5．4．1 合并排序 74

5．4．2 快速排序 76

5．4．3 排序算法的時(shí)間下界 80

5．5 選擇問題 82

5．5．1 分治法求解 82

5．5．2 隨機(jī)選擇主元 82

5．5．3 線性時(shí)間選擇算法 84

5．5．4 時(shí)間分析 86

5．5．5 允許重復(fù)元素的選擇算法 86

5．6 斯特拉森矩陣乘法 87

5．6．1 分治法求解 87

5．6．2 斯特拉森分治法 88

本章小結(jié) 88

習(xí)題5 88

第6章 貪心法 91

6．1 一般方法 91

6．2 背包問題 92

6．2．1 問題描述 92

6．2．2 貪心法求解 92

6．2．3 算法正確性 94

6．3 帶時(shí)限的作業(yè)排序 95

6．3．1 問題描述 95

6．3．2 貪心法求解 95

6．3．3 算法正確性 97

6．3．4 可行性判定 97

6．3．5 作業(yè)排序貪心算法 98

6．3．6 一種改進(jìn)算法 99

6．4 最佳合并模式 102

6．4．1 問題描述 102

6．4．2 貪心法求解 103

6．4．3 算法正確性 104

6．5 最小代價(jià)生成樹 105

6．5．1 問題描述 105

6．5．2 貪心法求解 105

6．5．3 普里姆算法 106

6．5．4 克魯斯卡爾算法 109

6．5．5 算法正確性 111

6．6 單源最短路徑 111

6．6．1 問題描述 112

6．6．2 貪心法求解 112

6．6．3 迪杰斯特拉算法 112

6．6．4 算法正確性 115

6．7 磁帶最優(yōu)存儲(chǔ) 116

6．7．1 單帶最優(yōu)存儲(chǔ) 116

6．7．2 多帶最優(yōu)存儲(chǔ) 117

6．8 貪心法的基本要素 119

6．8．1 最優(yōu)量度標(biāo)準(zhǔn) 119

6．8．2 最優(yōu)子結(jié)構(gòu) 119

本章小結(jié) 120

習(xí)題6 120

第7章 動(dòng)態(tài)規(guī)劃法 122

7．1 一般方法和基本要素 122

7．1．1 一般方法 122

7．1．2 基本要素 123

7．1．3 多段圖問題 123

7．1．4 資源分配問題 126

7．1．5 關(guān)鍵路徑問題 127

7．2 每對結(jié)點(diǎn)間的最短路徑 129

7．2．1 問題描述 129

7．2．2 動(dòng)態(tài)規(guī)劃法求解 130

7．2．3 弗洛伊德算法 131

7．2．4 算法正確性 132

7．3 矩陣連乘 132

7．3．1 問題描述 132

7．3．2 動(dòng)態(tài)規(guī)劃法求解 133

7．3．3 矩陣連乘算法 134

7．3．4 備忘錄方法 136

7．4 最長公共子序列 137

7．4．1 問題描述 137

7．4．2 動(dòng)態(tài)規(guī)劃法求解 137

7．4．3 最長公共子序列算法 138

7．4．4 算法的改進(jìn) 140

7．5 最優(yōu)二叉搜索樹 140

7．5．1 問題描述 140

7．5．2 動(dòng)態(tài)規(guī)劃法求解 141

7．5．3 最優(yōu)二叉搜索樹算法 143

7．6 0/1背包 144

7．6．1 問題描述 144

7．6．2 動(dòng)態(tài)規(guī)劃法求解 145

7．6．3 0/1背包算法框架 147

7．6．4 0/1背包算法 150

7．6．5 性能分析 152

7．6．6 使用啟發(fā)式方法 153

7．7 流水作業(yè)調(diào)度 154

7．7．1 問題描述 154

7．7．2 動(dòng)態(tài)規(guī)劃法求解 155

7．7．3 Johnson算法 157

本章小結(jié) 158

習(xí)題7 158

第8章 回溯法 160

8．1 一般方法 160

8．1．1 基本概念 160

8．1．2 剪枝函數(shù)和回溯法 161

8．1．3 回溯法的效率分析 163

8．2 n-皇后 163

8．2．1 問題描述 163

8．2．2 回溯法求解 164

8．2．3 n-皇后算法 165

8．2．4 時(shí)間分析 166

8．3 子集和數(shù) 167

8．3．1 問題描述 167

8．3．2 回溯法求解 167

8．3．3 子集和數(shù)算法 168

8．4 圖的著色 170

8．4．1 問題描述 170

8．4．2 回溯法求解 170

8．4．3 圖著色算法 171

8．4．4 時(shí)間分析 172

8．5 哈密頓環(huán) 172

8．5．1 問題描述 172

8．5．2 哈密頓環(huán)算法 173

8．6 0/1背包 174

8．6．1 問題描述 174

8．6．2 回溯法求解 174

8．6．3 限界函數(shù) 175

8．6．4 0/1背包算法 176

8．7 批處理作業(yè)調(diào)度 178

8．7．1 問題描述 178

8．7．2 回溯法求解 178

8．7．3 批處理作業(yè)調(diào)度算法 178

本章小結(jié) 180

習(xí)題8 180

第9章 分枝限界法 182

9．1 一般方法 182

9．1．1 分枝限界法概述 182

9．1．2 LC分枝限界法 184

9．1．3 15謎問題 185

9．2 求最優(yōu)解的分枝限界法 187

9．2．1 上下界函數(shù) 187

9．2．2 FIFO分枝限界法 188

9．2．3 LC分枝限界法 189

9．3 帶時(shí)限的作業(yè)排序 190

9．3．1 問題描述 190

9．3．2 分枝限界法求解 190

9．3．3 帶時(shí)限作業(yè)排序算法 191

9．4 0/1背包 193

9．4．1 問題描述 193

9．4．2 分枝限界法求解 194

9．4．3 0/1背包算法 195

9．5 旅行商問題 197

9．5．1 問題描述 197

9．5．2 分枝限界法求解 198

9．6 批處理作業(yè)調(diào)度 201

9．6．1 問題描述 201

9．6．2 分枝限界法求解 201

9．6．3 批處理作業(yè)調(diào)度算法 202

本章小結(jié) 205

習(xí)題9 205

第3部分 求解困難問題

第10章 NP完全問題 207

10．1 基本概念 207

10．1．1 不確定算法和不確定機(jī) 208

10．1．2 可滿足性問題 210

10．1．3 P類和NP類問題 211

10．1．4 NP難度和NP完全問題 211

10．2 Cook定理和證明 212

10．2．1 Cook定理 212

10．2．2 簡化的不確定機(jī)模型 212

10．2．3 證明Cook定理 214

10．3 一些典型的NP完全問題 217

10．3．1 最大集團(tuán) 217

10．3．2 頂點(diǎn)覆蓋 218

10．3．3 三元CNF可滿足性 219

10．3．4 圖的著色數(shù) 220

10．3．5 有向哈密頓環(huán) 221

10．3．6 恰切覆蓋 223

10．3．7 子集和數(shù) 225

10．3．8 分劃問題 225

本章小結(jié) 226

習(xí)題10 226

第11章 隨機(jī)算法 228

11．1 基本概念 228

11．1．1 隨機(jī)算法概述 228

11．1．2 隨機(jī)數(shù)發(fā)生器 228

11．1．3 隨機(jī)算法分類 228

11．2 拉斯維加斯算法 229

11．2．1 標(biāo)識(shí)重復(fù)元素算法 229

11．2．2 性能分析 230

11．3 蒙特卡羅算法 231

11．3．1 素?cái)?shù)測試問題 231

11．3．2 偽素?cái)?shù)測試 231

11．3．3 米勒-拉賓算法 232

11．3．4 性能分析 233

11．4 舍伍德算法 234

11．4．1 隨機(jī)快速排序算法 234

11．4．2 舍伍德算法的其他應(yīng)用 234

本章小結(jié) 234

習(xí)題11 235

第12章 近似算法 236

12．1 近似算法的性能 236

12．1．1 基本概念 236

12．1．2 絕對性能保證 236

12．1．3 相對性能保證 237

12．1．4 近似方案 238

12．2 絕對近似算法 238

12．2．1 最多程序存儲(chǔ)問題 238

12．2．2 NP難度絕對近似算法 239

12．3 ?-近似算法 240

12．3．1 頂點(diǎn)覆蓋近似算法 240

12．3．2 旅行商問題 241

12．3．3 NP難度?-近似旅行商問題 242

12．3．4 具有三角不等式性質(zhì)的旅行商問題 243

12．3．5 任務(wù)調(diào)度近似算法 244

12．4 ?(n)-近似算法 247

12．4．1 集合覆蓋問題 247

12．4．2 集合覆蓋近似算法 247

12．4．3 ln(n)-近似算法 248

12．5 多項(xiàng)式時(shí)間近似方案 249

12．5．1 任務(wù)調(diào)度近似方案 249

12．5．2 多項(xiàng)式時(shí)間近似方案 251

12．6 子集和數(shù)的完全多項(xiàng)式時(shí)間近似方案 251

12．6．1 子集和數(shù)的指數(shù)時(shí)間算法 251

12．6．2 完全多項(xiàng)式時(shí)間近似方案 252

本章小結(jié) 254

習(xí)題12 254

第13章 遺傳算法 256

13．1 進(jìn)化計(jì)算 256

13．2 遺傳算法的生物學(xué)基礎(chǔ) 257

13．3 遺傳算法的基本思想 258

13．4 基本遺傳算法 259

13．4．1 基本遺傳算法構(gòu)成要素 259

13．4．2 基本遺傳算法流程圖 262

13．5 遺傳算法的特點(diǎn)和應(yīng)用 262

13．5．1 遺傳算法的特點(diǎn) 262

13．5．2 遺傳算法的應(yīng)用 263

13．6 基本遺傳算法實(shí)現(xiàn)方法 263

13．6．1 數(shù)據(jù)結(jié)構(gòu) 263

13．6．2 主程序 264

13．6．3 選擇運(yùn)算 264

13．6．4 交叉運(yùn)算 266

13．6．5 變異運(yùn)算 267

13．7 旅行商問題 268

13．7．1 排列編碼 268

13．7．2 目標(biāo)函數(shù)和適應(yīng)度函數(shù) 269

13．7．3 錦標(biāo)賽選擇 269

13．7．4 順序交叉 269

13．7．5 交換變異 271

13．7．6 參數(shù)選擇 272

13．7．7 實(shí)例運(yùn)行結(jié)果 272

本章小結(jié) 272

習(xí)題13 272

第14章 密碼算法 274

14．1 信息安全和密碼學(xué) 274

14．1．1 信息安全 274

14．1．2 什么是密碼 274

14．1．3 密碼體制 275

14．2 數(shù)論初步 276

14．3 背包密碼算法 277

14．3．1 背包算法 277

14．3．2 超遞增背包 278

14．3．3 由私人密鑰產(chǎn)生公開密鑰 279

14．3．4 加密方法 279

14．3．5 解密方法 279

14．3．6 背包安全性 280

14．4 RSA算法 280

14．4．1 RSA算法概述 280

14．4．2 RSA的安全性 281

14．5 散列函數(shù)和消息認(rèn)證 282

14．5．1 散列函數(shù) 282

14．5．2 散列函數(shù)結(jié)構(gòu) 282

14．5．3 消息認(rèn)證 283

14．6 數(shù)字簽名 283

14．6．1 RSA數(shù)字簽名體制 283

14．6．2 需仲裁的數(shù)字簽名 284

本章小結(jié) 284

習(xí)題14 284

附錄A 專有名詞中英文對照表 285

附錄B C++程序設(shè)計(jì)概要 290

參考文獻(xiàn) 304