算法分析與設(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常見(jiàn)的算法時(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棋盤(pán)覆蓋問(wèn)題22
2.6.1問(wèn)題描述22
2.6.2算法復(fù)雜性分析25
2.7合并排序25
2.7.1基于比較的排序時(shí)間復(fù)雜度下界25
2.7.2用遞歸樹(shù)解遞歸關(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問(wèn)題描述32
2.9.2問(wèn)題的分治法設(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矩陣連乘問(wèn)題45
3.2.1問(wèn)題描述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重疊子問(wèn)題50
3.3.3備忘錄方法52
3.4最長(zhǎng)公共子序列問(wèn)題53
3.4.1問(wèn)題描述53
3.4.2最長(zhǎng)公共子序列的結(jié)構(gòu)54
3.4.3子問(wèn)題的遞歸結(jié)構(gòu)54
3.4.4計(jì)算最優(yōu)值55
3.4.5構(gòu)造最長(zhǎng)公共子序列56
3.4.6算法的改進(jìn)57
3.5凸多邊形的最優(yōu)三角剖分問(wèn)題57
3.5.1問(wèn)題描述57
3.5.2三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題58
3.5.3最優(yōu)子結(jié)構(gòu)性質(zhì)60
3.5.4最優(yōu)三角剖分對(duì)應(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問(wèn)題描述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)安排問(wèn)題74
4.1.1貪心算法設(shè)計(jì)的特點(diǎn)74
4.1.2問(wèn)題描述74
4.1.3活動(dòng)安排問(wèn)題的貪心算法 75
4.2貪心算法的基本要素76
4.2.1貪心選擇性質(zhì)76
4.2.2最優(yōu)子結(jié)構(gòu)性質(zhì)77
4.2.3貪心算法的求解過(guò)程77
4.2.4貪心算法與動(dòng)態(tài)規(guī)劃法的差異78
4.3最優(yōu)裝載79
4.3.1問(wèn)題描述79
4.3.2貪心選擇性質(zhì)79
4.3.3最優(yōu)子結(jié)構(gòu)性質(zhì)80
4.3.4算法描述80
4.4最短路徑問(wèn)題80
4.4.1問(wèn)題描述80
4.4.2算法基本思想81
4.4.3算法實(shí)現(xiàn)82
4.5哈夫曼編碼84
4.5.1哈夫曼樹(shù)84
4.5.2構(gòu)造一棵哈夫曼樹(shù)86
4.5.3哈夫曼編碼87
4.5.4算法分析與設(shè)計(jì)89
4.5.5哈夫曼算法的正確性91
4.6TSP問(wèn)題92
4.6.1TSP問(wèn)題研究進(jìn)展92
4.6.2最近鄰點(diǎn)貪心策略93
4.6.3最短鏈接貪心策略95
4.7最小生成樹(shù)96
4.7.1Prim算法（最近頂點(diǎn)策略）96
4.7.2Kruskal算法（最短邊策略）97
4.8套利問(wèn)題98
4.8.1套利問(wèn)題描述98
4.8.2問(wèn)題的貪心選擇性質(zhì)99
4.8.3問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)99
4.8.4算法實(shí)例99
習(xí)題4101
第5章回溯法/107
5.1回溯法的算法框架107
5.1.1明確定義問(wèn)題的解空間107
5.1.2運(yùn)用回溯法解題的步驟108
5.1.3回溯法的算法框架108
5.2n皇后問(wèn)題110
5.2.1問(wèn)題描述110
5.2.2算法設(shè)計(jì)110
5.2.3算法實(shí)現(xiàn)111
5.2.48皇后問(wèn)題的不等效解分析與實(shí)現(xiàn)111
5.3圖的m著色問(wèn)題117
5.3.1問(wèn)題描述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背包問(wèn)題128
6.2.2分支限界法解旅行商問(wèn)題130
6.2.3分支限界法解15謎問(wèn)題132
6.3單源最短路徑問(wèn)題136
6.3.1問(wèn)題描述136
6.3.2算法分析136
6.3.3分支限界算法實(shí)現(xiàn)137
6.4裝載問(wèn)題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蒙特卡羅算法的簡(jiǎn)單應(yīng)用171
7.3.3主元素問(wèn)題174
7.3.4素?cái)?shù)測(cè)試176
7.4拉斯維加斯算法181
7.4.1n皇后問(wèn)題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棋盤(pán)覆蓋問(wèn)題的分治法設(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)賽日程表安排問(wèn)題的分治法設(shè)計(jì)201
實(shí)驗(yàn)15最大子段和問(wèn)題的分治法設(shè)計(jì)203
實(shí)驗(yàn)2動(dòng)態(tài)規(guī)劃法上機(jī)實(shí)驗(yàn)204
實(shí)驗(yàn)21矩陣連乘問(wèn)題的動(dòng)態(tài)規(guī)劃法設(shè)計(jì)205
實(shí)驗(yàn)22最長(zhǎng)公共子序列的動(dòng)態(tài)規(guī)劃法設(shè)計(jì)207
實(shí)驗(yàn)23圖像壓縮問(wèn)題的動(dòng)態(tài)規(guī)劃法設(shè)計(jì)208
實(shí)驗(yàn)3貪心算法上機(jī)實(shí)驗(yàn)213
實(shí)驗(yàn)31找硬幣問(wèn)題的貪心算法設(shè)計(jì)214
實(shí)驗(yàn)32活動(dòng)安排問(wèn)題的貪心算法215
實(shí)驗(yàn)33單源最短路徑問(wèn)題的貪心算法設(shè)計(jì)216
實(shí)驗(yàn)4回溯法上機(jī)實(shí)驗(yàn)219
實(shí)驗(yàn)418皇后問(wèn)題的回溯法設(shè)計(jì)219
實(shí)驗(yàn)42圖的著色問(wèn)題的回溯法設(shè)計(jì)222
第9章算法自測(cè)卷/225
9.1算法自測(cè)卷1225
9.2算法自測(cè)卷2226
9.3算法自測(cè)卷3231
附錄習(xí)題參考答案/234
習(xí)題1參考答案234
習(xí)題2參考答案235
習(xí)題3參考答案237
習(xí)題4參考答案241
習(xí)題5參考答案246
習(xí)題6參考答案248
習(xí)題7參考答案252
算法自測(cè)卷1參考答案266
算法自測(cè)卷2參考答案268
算法自測(cè)卷3參考答案272