算法設計與分析基礎（第3版）

圖書簡介

作者基於豐富的教學經驗，開發了一套全新的算法分類方法。該少跨微分類法站在通用問題求解策略的高度，對現有大多數算法準確分類，從而引領讀者沿著一條清晰、一致、連貫的思路來探索算法設計與分析這一迷人領域。本書作為第3版，相對前版調整了多個章節的內容和順序，同時增加了一些算法，並擴展了算法的套用，使得具體算法和通用算法設計技術的對應更加清晰有序；各章累計增加了70道習題，其中包括一些有趣的謎題和面試問題。

圖書目錄

第1章緒論 1

1.1　什麼是算法 2

習題1.1 6

1.2　算法問題求解基礎 7

1.2.1理解問題 8

1.2.2　了解計算設備的性能 8

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

1.2.4　算法的設計技術 9

1.2.5　確定適當的數據結構 9

1.2.6　算法的描述 10

1.2.7　算法的正確性證明 10

1.2.8　算法的分析 11

1.2.9　為算法寫代碼 12

習題1.2 13

1.3　重要的問題類型 14

1.3.1　排序 15

1.3.2　查找 16

1.3.3　字元串處理 16

1.3.4　圖問題 16

1.3.5　組合問題 17

1.3.6　幾何問題 17

1.3.7　數值問題 18

習題1.3 18

1.4　基本數據結構 20

1.4.1　線性數據結構 20

1.4.2　圖 22

1.4.3　樹 25

1.4.4　集合與字典 28

習題1.4 29

小結 30

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

2.1　分析框架 33

2.1.1輸入規模的度量 33

2.1.2運行時簽端踏她間的度量單位 34

2.1.3增長次數 35

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

2.1.5分析框架概要 38

習付協雄題2.1 39

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

2.2.1非正式的介紹 40

2.2.2符號O 41

2.2.3符號 42

2.2.4符號 42

2.2.5漸近符號的有用特性 43

2.2.6利用極限比較增長次數 44

2.2.7基本的效率類型 45

習題2.2 46

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

習題2.3 52

2.4遞歸算法的數學分析 54

習題2.4 59

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

習題2.5 65

2.6算法的經驗分析 66

習題2.6 69

2.7算法可視法 70

小結 73

第3章蠻跨企辨力法 75

3.1選擇排序和冒泡排序 76

3.1.1選擇排序 76

3.1.2冒泡排序 77

習題3.1 78

3.2順序查找和蠻力字元串匹配 80

3.2.1順序查找 80

3.2.2蠻力字元串匹配 81

習題詢棕3.2 82

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

3.3.1最近對問題 83

3.3.2凸包問題 84

習題3.3 87

3.4窮舉查找 89

3.4.1旅行商問題 89

3.4.2背包問題 90

3.4.3分配問題簽說愚 91

習題3.4 93

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

3.5.1深度優先查找 94

3.5.2廣度優先查找 96

習題店灶騙炒3.5 98

小結 100

第4章減治法 101

4.1插入排序 103

習題4.1 105

4.2拓撲排序 106

習題4.2 109

4.3生成組合對象的算法 111

4.3.1生成排列 111

4.3.2生成子集 113

習題4.3 114

4.4減常因子算法 115

4.4.1折半查找 116

4.4.2假幣問題 117

4.4.3俄式乘法 118

4.4.4約瑟夫斯問題 119

習題4.4 120

4.5減可變規模算法 122

4.5.1計算中值和選擇問題 122

4.5.2插值查找 125

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

4.5.4拈遊戲 127

習題4.5 128

小結 129

第5章分治法 131

5.1合併排序 133

習題5.1 135

5.2快速排序 136

習題5.2 140

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

習題5.3 143

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

5.4.1大整數乘法 145

5.4.2Strassen矩陣乘法 146

習題5.4 148

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

5.5.1最近對問題 149

5.5.2凸包問題 151

習題5.5 153

小結 154

第6章變治法 155

6.1預排序 156

習題6.1 158

6.2高斯消去法 160

6.2.1LU分解 164

6.2.2計算矩陣的逆 165

6.2.3計算矩陣的行列式 166

習題6.2 167

6.3平衡查找樹 168

6.3.1AVL樹 169

6.3.22-3樹 173

習題6.3 174

6.4堆和堆排序 175

6.4.1堆的概念 176

6.4.2堆排序 180

習題6.4 181

6.5　霍納法則和二進制冪 182

6.5.1霍納法則 182

6.5.2二進制冪 184

習題6.5 186

6.6　問題化簡 187

6.6.1求最低公倍數 188

6.6.2計算圖中的路徑數量 189

6.6.3最佳化問題的化簡 189

6.6.4線性規劃 190

6.6.5簡化為圖問題 192

習題6.6 193

小結 194

第7章　時空權衡 196

7.1　計數排序 197

習題7.1 199

7.2　字元串匹配中的輸入增強技術 200

7.2.1　Horspool算法 201

7.2.2　Boyer-Moore算法 204

習題7.2 207

7.3　散列法 209

7.3.1　開散列(分離鏈) 210

7.3.2　閉散列(開式定址) 211

習題7.3 213

7.4　B樹 214

習題7.4 217

小結 218

第8章　動態規劃 219

8.1　三個基本例子 220

習題8.1 224

8.2　背包問題和記憶功能 226

8.2.1　背包問題 226

8.2.2　記憶化 227

習題8.2 229

8.3　最優二叉查找樹 230

習題8.3 234

8.4　Warshall算法和Floyd算法 235

8.4.1　Warshall算法 235

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

習題8.4 241

小結 242

第9章　貪婪技術 243

9.1　Prim算法 245

習題9.1 249

9.2　Kruskal算法 250

習題9.2 255

9.3　Dijkstra算法 256

習題9.3 259

9.4　哈夫曼樹及編碼 260

習題9.4 264

小結 265

第10章　疊代改進 266

10.1　單純形法 267

10.1.1線性規劃的幾何解釋 267

10.1.2單純形法概述 270

10.1.3單純形法其他要點 275

習題10.1 276

10.2最大流量問題 278

習題10.2 285

10.3二分圖的最大匹配 286

習題10.3 291

10.4穩定婚姻問題 292

習題10.4 295

小結 296

第11章　算法能力的極限 297

11.1　如何求下界 298

11.1.1　平凡下界 298

11.1.2　資訊理論下界 299

11.1.3　敵手下界 299

11.1.4　問題化簡 300

習題11.1 302

11.2　決策樹 302

11.2.1　排序的決策樹 303

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

習題11.2 306

11.3　P、NP和NP完全問題 308

11.3.1　P和NP問題 308

11.3.2　NP完全問題 311

習題11.3 314

11.4　數值算法的挑戰 316

習題11.4 322

小結 323

第12章　超越算法能力的極限 325

12.1　回溯法 325

12.1.1　n皇后問題 326

12.1.2　哈密頓迴路問題 328

12.1.3　子集和問題 328

12.1.4　一般性說明 329

習題12.1 331

12.2　分支界限法 332

12.2.1　分配問題 332

12.2.2　背包問題 335

12.2.3　旅行商問題 336

習題12.2 338

12.3　NP困難問題的近似算法 339

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

12.3.2　背包問題的近似算法 349

習題12.3 352

12.4　解非線性方程的算法 353

12.4.1　平分法 355

12.4.2　試位法 357

12.4.3　牛頓法 358

習題12.4 360

小結 361

跋 363

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

附錄B遞推關係簡明指南 369

習題提示 380

參考文獻 414

算法設計與分析基礎（第3版）

基本介紹

圖書簡介

圖書目錄

相關詞條

熱門詞條