算法設計與分析基礎（第3版 詳解版） Introduction to the Design and Analysis of Algorithms, 3/e

詳細目錄

第1章　導言 1

1.1　什麽是算法 3

習題1.1 8

1.2　算法問題求解基礎 9

1.2.1  理解問題 10

1.2.2  瞭解計算設備的性能 11

1.2.3  在精確和近似解法之間做出選擇 12

1.2.4  算法的設計技術 12

1.2.5  設計算法和數據結構 12

1.2.6  算法描述方法 13

1.2.7  算法的正確性證明 14

1.2.8  分析算法 14

1.2.9  為算法寫代碼 16

習題1.2 17

1.3　重要的問題類型 19

1.3.1  排序 19

1.3.2  查找 21

1.3.3  字符串處理 21

1.3.4  圖問題 22

1.3.5  組合問題 22

1.3.6  幾何問題 23

1.3.7  數值問題 23

習題1.3 24

1.4　基本數據結構 26

1.4.1  線性數據結構 26

1.4.2  圖 29

1.4.3  樹 32

1.4.4  集合與字典 36

習題1.4 38

本章要點小結 39

第2章　算法效率分析基礎 41

2.1　分析框架 42

2.1.1  度量輸入規模 43

2.1.2  運行時間的度量單位 44

2.1.3  增長量級 45

2.1.4  算法的最差、最優和平均效率 47

2.1.5  分析框架概要 50

習題2.1 50

2.2　漸近符號和基本效率類型 52

2.2.1  非正式的介紹 53

2.2.2  符號O 53

2.2.3  符號Ω 54

2.2.4  符號Θ 55

2.2.5  漸近符號的有用特性 56

2.2.6  利用極限比較增長量級 57

2.2.7  基本效率類別 58

習題2.2 60

2.3  非遞歸算法的數學分析 61

習題2.3 67

2.4  遞歸算法的數學分析 70

習題2.4 77

2.5　例題：計算第n個斐波那契數 80

習題2.5 84

2.6　算法的經驗分析 85

習題2.6 91

2.7　算法可視化 92

本章要點小結 95

第3章　蠻力法 97

3.1　選擇排序和冒泡排序 98

3.1.1  選擇排序 98

3.1.2  冒泡排序 100

習題3.1 102

3.2　順序查找和蠻力字符串匹配 103

3.2.1  順序查找 104

3.2.2  蠻力字符串匹配 104

習題3.2 106

3.3　最近對和凸包問題的蠻力算法 108

3.3.1  最近對問題 108

3.3.2  凸包問題 110

習題3.3 113

3.4　窮舉查找 115

3.4.1  旅行商問題 116

3.4.2  背包問題 117

3.4.3  分配問題 119

習題3.4 120

3.5　深度優先查找和廣度優先查找 122

3.5.1  深度優先查找 122

3.5.2  廣度優先查找 125

習題3.5 128

本章要點小結 130

第4章　減治法 132

4.1　插入排序 135

習題4.1 137

4.2　拓撲排序 140

習題4.2 143

4.3  生成組合對象的算法 145

4.3.1  生成排列 145

4.3.2  生成子集 148

習題4.3 150

4.4  減常因子算法 151

4.4.1  折半查找 152

4.4.2  假幣問題 154

4.4.3  俄式乘法 155

4.4.4  約瑟夫斯問題 156

習題4.4 158

4.5　減可變規模算法 160

4.5.1  計算中值和選擇問題 160

4.5.2  插值查找 164

4.5.3  二叉查找樹的查找和插入 165

4.5.4  尼姆游戲 166

習題4.5 168

本章要點小結 170

第5章　分治法 171

5.1　合並排序 173

習題5.1 176

5.2　快速排序 178

習題5.2 183

5.3　二叉樹遍歷及其相關特性 185

習題5.3 188

5.4　大整數乘法和Strassen矩陣乘法 189

5.4.1  大整數乘法 190

5.4.2  Strassen矩陣乘法 192

習題5.4 194

5.5　用分治法解最近對問題和凸包問題 195

5.5.1  最近對問題 195

5.5.2  凸包問題 198

習題5.5 200

本章要點小結 201

第6章　變治法 203

6.1　預排序 204

習題6.1 207

6.2　高斯消去法 210

6.2.1  LU分解 215

6.2.2  計算矩陣的逆 216

6.2.3  計算矩陣的行列式 217

習題6.2 218

6.3　平衡查找樹 220

6.3.1  平衡二叉查找樹 221

6.3.2  2-3樹 225

習題6.3 228

6.4　堆和堆排序 229

6.4.1  堆的概念 229

6.4.2  堆排序 234

習題6.4 235

6.5　霍納法則和二進制冪 236

6.5.1  霍納法則 237

6.5.2  二進制冪 239

習題6.5 242

6.6　問題化簡 243

6.6.1  求最小公倍數 244

6.6.2  計算圖中的路徑數量 245

6.6.3  最優化問題的化簡 246

6.6.4  線性規劃 247

6.6.5  簡化為圖問題 250

習題6.6 251

本章要點小結 253

第7章　時空權衡 255

7.1　計數排序 256

習題7.1 260

7.2　字符串匹配中的輸入增強技術 261

7.2.1　Horspool算法 262

7.2.2　Boyer-Moore算法 265

習題7.2 270

7.3　散列法 271

7.3.1　開散列(分離鏈) 273

7.3.2　閉散列(開式尋址) 275

習題7.3 278

7.4　B樹 279

習題7.4 283

本章要點小結 284

第8章　動態規劃 285

8.1　三個基本例子 287

習題8.1 292

8.2　背包問題和記憶功能 295

8.2.1  背包問題 295

8.2.2　記憶功能 297

習題8.2 298

8.3　最優二叉查找樹 299

習題8.3 304

8.4　Warshall算法和Floyd算法 305

8.4.1　Warshall算法 306

8.4.2　計算完全最短路徑的Floyd算法 309

習題8.4 313

本章要點小結 314

第9章　貪婪技術 315

9.1　Prim算法 318

習題9.1 323

9.2　Kruskal算法 325

習題9.2 332

9.3　Dijkstra算法 334

習題9.3 338

9.4　哈夫曼樹及編碼 339

習題9.4 343

本章要點小結 344

第10章　迭代改進 346

10.1　單純形法 347

10.1.1  線性規劃的幾何解釋 348

10.1.2  單純形法概述 352

10.1.3  單純形法其他要點 358

習題10.1 360

10.2　最大流量問題 362

習題10.2 372

10.3　二分圖的最大匹配 373

習題10.3 380

10.4　穩定婚姻問題 382

習題10.4 386

本章要點小結 387

第11章　算法能力的極限 388

11.1　如何求下界 389

11.1.1　平凡下界 390

11.1.2　信息論下界 391

11.1.3　敵手下界 391

11.1.4　問題化簡 393

習題11.1 394

11.2　決策樹 396

11.2.1　排序的決策樹 397

11.2.2　查找有序數組的決策樹 399

習題11.2 401

11.3　P、NP和NP完全問題 403

11.3.1　P和NP問題 403

11.3.2　NP完全問題 407

習題11.3 411

11.4　數值算法的挑戰 414

習題11.4 421

本章要點小結 422

第12章　應對算法能力的極限 425

12.1　回溯法 426

12.1.1　n皇後問題 427

12.1.2　哈密頓迴路問題 428

12.1.3　子集和問題 429

12.1.4　概括性說明 430

習題12.1 432

12.2　分支定界法 434

12.2.1　分配問題 435

12.2.2　背包問題 437

12.2.3　旅行商問題 440

習題12.2 442

12.3　NP難題的近似算法 443

12.3.1　旅行商問題的近似算法 445

12.3.2　背包問題的近似算法 454

習題12.3 459

12.4　解非線性方程的算法 460

12.4.1　對分法 462

12.4.2　試位法 465

12.4.3　牛頓法 466

習題12.4 468

本章要點小結 469

後記 472

附錄A　算法分析的實用公式 477

附錄B　遞推關系簡明指南 480

參考文獻 494