算法分析與設計

第1章算法概述/1
1.1什么是算法1
1.2算法復雜性2
1.3算法復雜性計量3
1.4算法復雜性的表示4
1.4.1算法復雜性的漸近性態(tài)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
〖1〗算法分析與設計目錄〖3〗〖3〗2.8.1算法描述30
2.8.2時間復雜度分析32
2.9循環(huán)賽日程表安排32
2.9.1問題描述32
2.9.2問題的分治法設計思想33
2.9.3分治算法實現33
習題234
第3章動態(tài)規(guī)劃法/41
3.1動態(tài)規(guī)劃法概述41
3.1.1最優(yōu)性原理41
3.1.2動態(tài)規(guī)劃法的基本步驟41
3.2矩陣連乘問題45
3.2.1問題描述45
3.2.2分析最優(yōu)解的結構47
3.2.3建立遞歸關系47
3.2.4計算最優(yōu)值48
3.2.5構造最優(yōu)解49
3.3動態(tài)規(guī)劃算法的基本要素50
3.3.1最優(yōu)子結構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計算最優(yōu)值55
3.4.5構造最長公共子序列56
3.4.6算法的改進57
3.5凸多邊形的最優(yōu)三角剖分問題57
3.5.1問題描述57
3.5.2三角剖分的結構及其相關問題58
3.5.3最優(yōu)子結構性質60
3.5.4最優(yōu)三角剖分對應的權的遞歸結構60
3.5.5計算最優(yōu)值60
3.5.6構造最優(yōu)三角剖分61
3.6多邊形游戲61
3.6.1問題描述61
3.6.2最優(yōu)子結構性質 62
3.6.3遞歸求解63
3.6.4算法描述63
3.7圖像壓縮65
3.7.1圖像壓縮實例65
3.7.2最優(yōu)子結構性質67
3.7.3遞歸計算最優(yōu)值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最優(yōu)子結構性質77
4.2.3貪心算法的求解過程77
4.2.4貪心算法與動態(tài)規(guī)劃法的差異78
4.3最優(yōu)裝載79
4.3.1問題描述79
4.3.2貪心選擇性質79
4.3.3最優(yōu)子結構性質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問題的最優(yōu)子結構性質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構造最優(yōu)解143
6.4.4最大收益分支限界（優(yōu)先隊列式）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循環(huán)賽日程表安排問題的分治法設計201
實驗15最大子段和問題的分治法設計203
實驗2動態(tài)規(guī)劃法上機實驗204
實驗21矩陣連乘問題的動態(tài)規(guī)劃法設計205
實驗22最長公共子序列的動態(tài)規(guī)劃法設計207
實驗23圖像壓縮問題的動態(tài)規(guī)劃法設計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