算法分析與設(shè)計(jì)

第1章算法概述/1
1.1什么是算法1
1.2算法復(fù)雜性2
1.3算法復(fù)雜性計(jì)量3
1.4算法復(fù)雜性的表示4
1.4.1算法復(fù)雜性的漸近性態(tài)4
1.4.2復(fù)雜性漸近階5
1.4.35個(gè)漸近意義下的記號(hào) 5
1.4.4常見的算法時(shí)間復(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ù)乘積的時(shí)間復(fù)雜度遞推方程21
2.5Strassen矩陣乘法21
2.5.1Strassen矩陣分治乘法21
2.5.2時(shí)間復(fù)雜度遞推方程22
2.6棋盤覆蓋問題22
2.6.1問題描述22
2.6.2算法復(fù)雜性分析25
2.7合并排序25
2.7.1基于比較的排序時(shí)間復(fù)雜度下界25
2.7.2用遞歸樹解遞歸關(guān)系式26
2.7.3合并排序27
2.8快速排序30
〖1〗算法分析與設(shè)計(jì)目錄〖3〗〖3〗2.8.1算法描述30
2.8.2時(shí)間復(fù)雜度分析32
2.9循環(huán)賽日程表安排32
2.9.1問題描述32
2.9.2問題的分治法設(shè)計(jì)思想33
2.9.3分治算法實(shí)現(xiàn)33
習(xí)題234
第3章動(dòng)態(tài)規(guī)劃法/41
3.1動(dòng)態(tài)規(guī)劃法概述41
3.1.1最優(yōu)性原理41
3.1.2動(dòng)態(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計(jì)算最優(yōu)值48
3.2.5構(gòu)造最優(yōu)解49
3.3動(dòng)態(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計(jì)算最優(yōu)值55
3.4.5構(gòu)造最長公共子序列56
3.4.6算法的改進(jìn)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計(jì)算最優(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圖像壓縮實(shí)例65
3.7.2最優(yōu)子結(jié)構(gòu)性質(zhì)67
3.7.3遞歸計(jì)算最優(yōu)值67
3.7.4算法實(shí)現(xiàn)68
習(xí)題370
第4章貪心算法/74
4.1活動(dòng)安排問題74
4.1.1貪心算法設(shè)計(jì)的特點(diǎn)74
4.1.2問題描述74
4.1.3活動(dòng)安排問題的貪心算法 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貪心算法與動(dòng)態(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算法實(shí)現(xiàn)82
4.5哈夫曼編碼84
4.5.1哈夫曼樹84
4.5.2構(gòu)造一棵哈夫曼樹86
4.5.3哈夫曼編碼87
4.5.4算法分析與設(shè)計(jì)89
4.5.5哈夫曼算法的正確性91
4.6TSP問題92
4.6.1TSP問題研究進(jìn)展92
4.6.2最近鄰點(diǎn)貪心策略93
4.6.3最短鏈接貪心策略95
4.7最小生成樹96
4.7.1Prim算法（最近頂點(diǎn)策略）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算法實(shí)例99
習(xí)題4101
第5章回溯法/107
5.1回溯法的算法框架107
5.1.1明確定義問題的解空間107
5.1.2運(yùn)用回溯法解題的步驟108
5.1.3回溯法的算法框架108
5.2n皇后問題110
5.2.1問題描述110
5.2.2算法設(shè)計(jì)110
5.2.3算法實(shí)現(xiàn)111
5.2.48皇后問題的不等效解分析與實(shí)現(xiàn)111
5.3圖的m著色問題117
5.3.1問題描述117
5.3.2算法實(shí)現(xiàn)119
5.4回溯法的效率分析120
5.4.1重排原理120
5.4.2估算結(jié)點(diǎn)數(shù)120
5.4.3回溯法的效率122
習(xí)題5122
第6章分支限界法/127
6.1分支限界法的基本思想127
6.2分支限界法的算法實(shí)例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分支限界算法實(shí)現(xiàn)137
6.4裝載問題141
6.4.1隊(duì)列式分支限界法141
6.4.2算法的改進(jìn)143
6.4.3構(gòu)造最優(yōu)解143
6.4.4最大收益分支限界（優(yōu)先隊(duì)列式）144
習(xí)題6145
第7章概率算法/147
7.1隨機(jī)數(shù)147
7.2數(shù)值概率算法152
7.2.1用隨機(jī)投點(diǎn)法計(jì)算π值152
7.2.2計(jì)算定積分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素?cái)?shù)測試176
7.4拉斯維加斯算法181
7.4.1n皇后問題181
7.4.2整數(shù)因子分解187
7.5舍伍德算法188
7.5.1線性時(shí)間選擇算法189
7.5.2跳躍表191
習(xí)題7193
第8章實(shí)驗(yàn)指導(dǎo)/195
實(shí)驗(yàn)1分治法上機(jī)實(shí)驗(yàn)195
實(shí)驗(yàn)11棋盤覆蓋問題的分治法設(shè)計(jì)195
實(shí)驗(yàn)12利用分治法實(shí)現(xiàn)合并排序197
實(shí)驗(yàn)13用分治法實(shí)現(xiàn)快速排序算法200
實(shí)驗(yàn)14循環(huán)賽日程表安排問題的分治法設(shè)計(jì)201
實(shí)驗(yàn)15最大子段和問題的分治法設(shè)計(jì)203
實(shí)驗(yàn)2動(dòng)態(tài)規(guī)劃法上機(jī)實(shí)驗(yàn)204
實(shí)驗(yàn)21矩陣連乘問題的動(dòng)態(tài)規(guī)劃法設(shè)計(jì)205
實(shí)驗(yàn)22最長公共子序列的動(dòng)態(tài)規(guī)劃法設(shè)計(jì)207
實(shí)驗(yàn)23圖像壓縮問題的動(dòng)態(tài)規(guī)劃法設(shè)計(jì)208
實(shí)驗(yàn)3貪心算法上機(jī)實(shí)驗(yàn)213
實(shí)驗(yàn)31找硬幣問題的貪心算法設(shè)計(jì)214
實(shí)驗(yàn)32活動(dòng)安排問題的貪心算法215
實(shí)驗(yàn)33單源最短路徑問題的貪心算法設(shè)計(jì)216
實(shí)驗(yàn)4回溯法上機(jī)實(shí)驗(yàn)219
實(shí)驗(yàn)418皇后問題的回溯法設(shè)計(jì)219
實(shí)驗(yàn)42圖的著色問題的回溯法設(shè)計(jì)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