算法分析與設計

本書主要介紹經典的算法設計技術，包括遞歸與分治策略、動態規劃法、貪心算法、回溯法、分支限界法、概率算法等。在算法分析方面，介紹了二分搜索技術、大整數的乘法、Strassen矩陣乘法、棋盤覆蓋、合併排序、快速排序、循環賽日程表、矩陣連乘問題、最長公共子序列、凸多邊形**三角剖分、多邊形遊戲、圖像壓縮、活動安排問題、**裝載、哈夫曼編碼、最小生成樹問題、套利問題、n皇后問題、圖的m着色問題、15謎問題、單源最短路徑問題、旅行商問題等，並對有的問題進行算法優化設計。書中主要突出對問題本身的分析和求解方法，並進行了問題的計算複雜性分析。本書每章均精選了一些基礎的算法習題,針對各章節不同的算法設計技術設計了多個上機實驗，並提供多套自測試卷,有助於學生了解自己對學習內容的掌握程度,自測學習效果。 ^[1] 

目錄

第1章算法概述/1

1.1什麼是算法1

1.2算法複雜性2

1.3算法複雜性計量3

1.4算法複雜性的表示4

1.4.1算法複雜性的漸近性態4

1.4.2複雜性漸近階5

1.4.35個漸近意義下的記號 5

1.4.4常見的算法時間複雜度6

1.5算法複雜性的重要性7

習題18

第2章遞歸與分治策略 /11

2.1遞歸的概念11

2.2分治法的基本思想16

2.3二分搜索技術18

2.3.1線性查找18

2.3.2二分搜索法18

2.3.3二分搜索算法複雜性最壞情形分析19

2.3.4二分搜索算法複雜性平均情形分析20

2.4大整數的乘法20

2.4.1大整數乘積的分治算法描述20

2.4.2大整數乘積的時間複雜度遞推方程21

2.5Strassen矩陣乘法21

2.5.1Strassen矩陣分治乘法21

2.5.2時間複雜度遞推方程22

2.6棋盤覆蓋問題22

2.6.1問題描述22

2.6.2算法複雜性分析25

2.7合併排序25

2.7.1基於比較的排序時間複雜度下界25

2.7.2用遞歸樹解遞歸關係式26

2.7.3合併排序27

2.8快速排序30

2.8.1算法描述30

2.8.2時間複雜度分析32

2.9循環賽日程表安排32

2.9.1問題描述32

2.9.2問題的分治法設計思想33

2.9.3分治算法實現33

習題234

第3章動態規劃法/41

3.1動態規劃法概述41

3.1.1最優性原理41

3.1.2動態規劃法的基本步驟41

3.2矩陣連乘問題45

3.2.1問題描述45

3.2.2分析最優解的結構47

3.2.3建立遞歸關係47

3.2.4計算最優值48

3.2.5構造最優解49

3.3動態規劃算法的基本要素50

3.3.1最優子結構50

3.3.2重疊子問題50

3.3.3備忘錄方法52

3.4最長公共子序列問題53

3.4.1問題描述53

3.4.2最長公共子序列的結構54

3.4.3子問題的遞歸結構54

3.4.4計算最優值55

3.4.5構造最長公共子序列56

3.4.6算法的改進57

3.5凸多邊形的最優三角剖分問題57

3.5.1問題描述57

3.5.2三角剖分的結構及其相關問題58

3.5.3最優子結構性質60

3.5.4最優三角剖分對應的權的遞歸結構60

3.5.5計算最優值60

3.5.6構造最優三角剖分61

3.6多邊形遊戲61

3.6.1問題描述61

3.6.2最優子結構性質 62

3.6.3遞歸求解63

3.6.4算法描述63

3.7圖像壓縮65

3.7.1圖像壓縮實例65

3.7.2最優子結構性質67

3.7.3遞歸計算最優值67

3.7.4算法實現68

習題370

第4章貪心算法/74

4.1活動安排問題74

4.1.1貪心算法設計的特點74

4.1.2問題描述74

4.1.3活動安排問題的貪心算法 75

4.2貪心算法的基本要素76

4.2.1貪心選擇性質76

4.2.2最優子結構性質77

4.2.3貪心算法的求解過程77

4.2.4貪心算法與動態規劃法的差異78

4.3最優裝載79

4.3.1問題描述79

4.3.2貪心選擇性質79

4.3.3最優子結構性質80

4.3.4算法描述80

4.4最短路徑問題80

4.4.1問題描述80

4.4.2算法基本思想81

4.4.3算法實現82

4.5哈夫曼編碼84

4.5.1哈夫曼樹84

4.5.2構造一棵哈夫曼樹86

4.5.3哈夫曼編碼87

4.5.4算法分析與設計89

4.5.5哈夫曼算法的正確性91

4.6TSP問題92

4.6.1TSP問題研究進展92

4.6.2最近鄰點貪心策略93

4.6.3最短鏈接貪心策略95

4.7最小生成樹96

4.7.1Prim算法（最近頂點策略）96

4.7.2Kruskal算法（最短邊策略）97

4.8套利問題98

4.8.1套利問題描述98

4.8.2問題的貪心選擇性質99

4.8.3問題的最優子結構性質99

4.8.4算法實例99

習題4101

第5章回溯法/107

5.1回溯法的算法框架107

5.1.1明確定義問題的解空間107

5.1.2運用回溯法解題的步驟108

5.1.3回溯法的算法框架108

5.2n皇后問題110

5.2.1問題描述110

5.2.2算法設計110

5.2.3算法實現111

5.2.48皇后問題的不等效解分析與實現111

5.3圖的m着色問題117

5.3.1問題描述117

5.3.2算法實現119

5.4回溯法的效率分析120

5.4.1重排原理120

5.4.2估算結點數120

5.4.3回溯法的效率122

習題5122

第6章分支限界法/127

6.1分支限界法的基本思想127

6.2分支限界法的算法實例128

6.2.1分支限界法解01揹包問題128

6.2.2分支限界法解旅行商問題130

6.2.3分支限界法解15謎問題132

6.3單源最短路徑問題136

6.3.1問題描述136

6.3.2算法分析136

6.3.3分支限界算法實現137

6.4裝載問題141

6.4.1隊列式分支限界法141

6.4.2算法的改進143

6.4.3構造最優解143

6.4.4最大收益分支限界（優先隊列式）144

習題6145

第7章概率算法/147

7.1隨機數147

7.2數值概率算法152

7.2.1用隨機投點法計算π值152

7.2.2計算定積分154

7.2.3解非線性方程158

7.2.4解非線性方程組160

7.3蒙特卡羅算法170

7.3.1蒙特卡羅算法的基本思想170

7.3.2蒙特卡羅算法的簡單應用171

7.3.3主元素問題174

7.3.4素數測試176

7.4拉斯維加斯算法181

7.4.1n皇后問題181

7.4.2整數因子分解187

7.5舍伍德算法188

7.5.1線性時間選擇算法189

7.5.2跳躍表191

習題7193

第8章實驗指導/195

實驗1分治法上機實驗195

實驗11棋盤覆蓋問題的分治法設計195

實驗12利用分治法實現合併排序197

實驗13用分治法實現快速排序算法200

實驗14循環賽日程表安排問題的分治法設計201

實驗15最大子段和問題的分治法設計203

實驗2動態規劃法上機實驗204

實驗21矩陣連乘問題的動態規劃法設計205

實驗22最長公共子序列的動態規劃法設計207

實驗23圖像壓縮問題的動態規劃法設計208

實驗3貪心算法上機實驗213

實驗31找硬幣問題的貪心算法設計214

實驗32活動安排問題的貪心算法215

實驗33單源最短路徑問題的貪心算法設計216

實驗4回溯法上機實驗219

實驗418皇后問題的回溯法設計219

實驗42圖的着色問題的回溯法設計222

第9章算法自測卷/225

9.1算法自測卷1225

9.2算法自測卷2226

9.3算法自測卷3231

附錄習題參考答案/234

習題1參考答案234

習題2參考答案235

習題3參考答案237

習題4參考答案241

習題5參考答案246

習題6參考答案248

習題7參考答案252

算法自測卷1參考答案266

算法自測卷2參考答案268

算法自測卷3參考答案272 ^[2]