算法分析與設(shè)計

第1章算法概述/1
1.1什么是算法1
1.2算法復(fù)雜性2
1.3算法復(fù)雜性計量3
1.4算法復(fù)雜性的表示4
1.4.1算法復(fù)雜性的漸近性態(tài)4
1.4.2復(fù)雜性漸近階5
1.4.35個漸近意義下的記號 5
1.4.4常見的算法時間復(fù)雜度6
1.5算法復(fù)雜性的重要性7
習(xí)題18
第2章遞歸與分治策略 /11
2.1遞歸的概念11
2.2分治法的基本思想16
2.3二分搜索技術(shù)18
2.3.1線性查找18
2.3.2二分搜索法18
2.3.3二分搜索算法復(fù)雜性最壞情形分析19
2.3.4二分搜索算法復(fù)雜性平均情形分析20
2.4大整數(shù)的乘法20
2.4.1大整數(shù)乘積的分治算法描述20
2.4.2大整數(shù)乘積的時間復(fù)雜度遞推方程21
2.5Strassen矩陣乘法21
2.5.1Strassen矩陣分治乘法21
2.5.2時間復(fù)雜度遞推方程22
2.6棋盤覆蓋問題22
2.6.1問題描述22
2.6.2算法復(fù)雜性分析25
2.7合并排序25
2.7.1基于比較的排序時間復(fù)雜度下界25
2.7.2用遞歸樹解遞歸關(guān)系式26
2.7.3合并排序27
2.8快速排序30
〖1〗算法分析與設(shè)計目錄〖3〗〖3〗2.8.1算法描述30
2.8.2時間復(fù)雜度分析32
2.9循環(huán)賽日程表安排32
2.9.1問題描述32
2.9.2問題的分治法設(shè)計思想33
2.9.3分治算法實現(xiàn)33
習(xí)題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)解的結(jié)構(gòu)47
3.2.3建立遞歸關(guān)系47
3.2.4計算最優(yōu)值48
3.2.5構(gòu)造最優(yōu)解49
3.3動態(tài)規(guī)劃算法的基本要素50
3.3.1最優(yōu)子結(jié)構(gòu)50
3.3.2重疊子問題50
3.3.3備忘錄方法52
3.4最長公共子序列問題53
3.4.1問題描述53
3.4.2最長公共子序列的結(jié)構(gòu)54
3.4.3子問題的遞歸結(jié)構(gòu)54
3.4.4計算最優(yōu)值55
3.4.5構(gòu)造最長公共子序列56
3.4.6算法的改進57
3.5凸多邊形的最優(yōu)三角剖分問題57
3.5.1問題描述57
3.5.2三角剖分的結(jié)構(gòu)及其相關(guān)問題58
3.5.3最優(yōu)子結(jié)構(gòu)性質(zhì)60
3.5.4最優(yōu)三角剖分對應(yīng)的權(quán)的遞歸結(jié)構(gòu)60
3.5.5計算最優(yōu)值60
3.5.6構(gòu)造最優(yōu)三角剖分61
3.6多邊形游戲61
3.6.1問題描述61
3.6.2最優(yōu)子結(jié)構(gòu)性質(zhì) 62
3.6.3遞歸求解63
3.6.4算法描述63
3.7圖像壓縮65
3.7.1圖像壓縮實例65
3.7.2最優(yōu)子結(jié)構(gòu)性質(zhì)67
3.7.3遞歸計算最優(yōu)值67
3.7.4算法實現(xiàn)68
習(xí)題370
第4章貪心算法/74
4.1活動安排問題74
4.1.1貪心算法設(shè)計的特點74
4.1.2問題描述74
4.1.3活動安排問題的貪心算法 75
4.2貪心算法的基本要素76
4.2.1貪心選擇性質(zhì)76
4.2.2最優(yōu)子結(jié)構(gòu)性質(zhì)77
4.2.3貪心算法的求解過程77
4.2.4貪心算法與動態(tài)規(guī)劃法的差異78
4.3最優(yōu)裝載79
4.3.1問題描述79
4.3.2貪心選擇性質(zhì)79
4.3.3最優(yōu)子結(jié)構(gòu)性質(zhì)80
4.3.4算法描述80
4.4最短路徑問題80
4.4.1問題描述80
4.4.2算法基本思想81
4.4.3算法實現(xiàn)82
4.5哈夫曼編碼84
4.5.1哈夫曼樹84
4.5.2構(gòu)造一棵哈夫曼樹86
4.5.3哈夫曼編碼87
4.5.4算法分析與設(shè)計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問題的貪心選擇性質(zhì)99
4.8.3問題的最優(yōu)子結(jié)構(gòu)性質(zhì)99
4.8.4算法實例99
習(xí)題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算法設(shè)計110
5.2.3算法實現(xiàn)111
5.2.48皇后問題的不等效解分析與實現(xiàn)111
5.3圖的m著色問題117
5.3.1問題描述117
5.3.2算法實現(xiàn)119
5.4回溯法的效率分析120
5.4.1重排原理120
5.4.2估算結(jié)點數(shù)120
5.4.3回溯法的效率122
習(xí)題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分支限界算法實現(xiàn)137
6.4裝載問題141
6.4.1隊列式分支限界法141
6.4.2算法的改進143
6.4.3構(gòu)造最優(yōu)解143
6.4.4最大收益分支限界（優(yōu)先隊列式）144
習(xí)題6145
第7章概率算法/147
7.1隨機數(shù)147
7.2數(shù)值概率算法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蒙特卡羅算法的簡單應(yīng)用171
7.3.3主元素問題174
7.3.4素數(shù)測試176
7.4拉斯維加斯算法181
7.4.1n皇后問題181
7.4.2整數(shù)因子分解187
7.5舍伍德算法188
7.5.1線性時間選擇算法189
7.5.2跳躍表191
習(xí)題7193
第8章實驗指導(dǎo)/195
實驗1分治法上機實驗195
實驗11棋盤覆蓋問題的分治法設(shè)計195
實驗12利用分治法實現(xiàn)合并排序197
實驗13用分治法實現(xiàn)快速排序算法200
實驗14循環(huán)賽日程表安排問題的分治法設(shè)計201
實驗15最大子段和問題的分治法設(shè)計203
實驗2動態(tài)規(guī)劃法上機實驗204
實驗21矩陣連乘問題的動態(tài)規(guī)劃法設(shè)計205
實驗22最長公共子序列的動態(tài)規(guī)劃法設(shè)計207
實驗23圖像壓縮問題的動態(tài)規(guī)劃法設(shè)計208
實驗3貪心算法上機實驗213
實驗31找硬幣問題的貪心算法設(shè)計214
實驗32活動安排問題的貪心算法215
實驗33單源最短路徑問題的貪心算法設(shè)計216
實驗4回溯法上機實驗219
實驗418皇后問題的回溯法設(shè)計219
實驗42圖的著色問題的回溯法設(shè)計222
第9章算法自測卷/225
9.1算法自測卷1225
9.2算法自測卷2226
9.3算法自測卷3231
附錄習(xí)題參考答案/234
習(xí)題1參考答案234
習(xí)題2參考答案235
習(xí)題3參考答案237
習(xí)題4參考答案241
習(xí)題5參考答案246
習(xí)題6參考答案248
習(xí)題7參考答案252
算法自測卷1參考答案266
算法自測卷2參考答案268
算法自測卷3參考答案272