1.1算法的概念1
1.2算法的表達(dá)1
1.2.1自然語(yǔ)言1
1.2.2結(jié)構(gòu)化圖形工具2
1.2.3計(jì)算機(jī)高級(jí)語(yǔ)言3
1.3算法的評(píng)價(jià)3
1.3.1算法的正確性4
1.3.2算法的空間復(fù)雜性5
1.3.3算法的時(shí)間復(fù)雜性5
1.4最差時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性6
1.5函數(shù)的階與漸進(jìn)性分析7
1.5.1復(fù)雜性函數(shù)的階7
1.5.2函數(shù)的漸進(jìn)性階的比較8
1.5.3函數(shù)的漸進(jìn)性階的運(yùn)算8
1.5.4函數(shù)的漸進(jìn)性表示與函數(shù)集合9
1.6本章習(xí)題9
第2章遞推與遞歸/10
2.1遞推關(guān)系與遞推算法10
2.2遞歸函數(shù)21
2.3遞歸函數(shù)的執(zhí)行過(guò)程22
2.4遞歸函數(shù)的時(shí)間復(fù)雜性與遞歸樹24
2.5估計(jì)遞歸函數(shù)的復(fù)雜度的主方法26
2.6本章習(xí)題27
第3章分治法/29
3.1二分搜索算法29
3.1.1問(wèn)題分析與算法設(shè)計(jì)29
3.1.2時(shí)間復(fù)雜性分析30
〖1〗算法設(shè)計(jì)與分析目錄[3]〖3〗3.2合并排序算法30
3.2.1問(wèn)題分析與算法設(shè)計(jì)31
3.2.2Merge函數(shù)31
3.2.3時(shí)間復(fù)雜性分析32
3.3快速排序算法32
3.3.1固定主元的快速排序32
3.3.2隨機(jī)選主元的快速排序34
3.4搜索第k元35
3.4.1平均時(shí)間為線性36
3.4.2最差時(shí)間為線性37
3.5最近點(diǎn)對(duì)39
3.5.1一維空間中的最近點(diǎn)對(duì)39
3.5.2二維空間中的最近點(diǎn)對(duì)40
3.6本章習(xí)題44
第4章動(dòng)態(tài)規(guī)劃/45
4.1遞歸方法中的重復(fù)計(jì)算45
4.2最長(zhǎng)公共子序列47
4.2.1問(wèn)題描述47
4.2.2遞推關(guān)系分析47
4.2.3算法實(shí)現(xiàn)48
4.3最大子段和49
4.3.1問(wèn)題描述49
4.3.2遞推分析49
4.3.3算法實(shí)現(xiàn)50
4.4矩陣連乘問(wèn)題51
4.4.1問(wèn)題描述51
4.4.2遞推分析52
4.4.3算法實(shí)現(xiàn)52
4.5數(shù)據(jù)壓縮問(wèn)題53
4.5.1問(wèn)題描述53
4.5.2遞推分析54
4.5.3算法實(shí)現(xiàn)55
4.60��1背包問(wèn)題56
4.6.1問(wèn)題描述56
4.6.2遞推分析56
4.6.3算法描述56
4.7消費(fèi)和儲(chǔ)蓄問(wèn)題57
4.7.1問(wèn)題描述57
4.7.2遞推分析58
4.7.3算法實(shí)現(xiàn)58
4.8最優(yōu)二叉搜索樹問(wèn)題59
4.8.1問(wèn)題描述59
4.8.2遞推分析60
4.8.3算法實(shí)現(xiàn)60
4.9本章習(xí)題61
第5章貪心算法/63
5.1活動(dòng)安排問(wèn)題64
5.1.1問(wèn)題描述64
5.1.2問(wèn)題分析64
5.1.3算法實(shí)現(xiàn)64
5.2服務(wù)調(diào)度問(wèn)題65
5.2.1問(wèn)題描述65
5.2.2問(wèn)題分析66
5.2.3算法實(shí)現(xiàn)66
5.3最遲時(shí)間限制服務(wù)調(diào)度問(wèn)題67
5.3.1問(wèn)題描述67
5.3.2問(wèn)題分析67
5.3.3算法實(shí)現(xiàn)69
5.4ε�脖嘲鼏�(wèn)題70
5.4.1問(wèn)題描述70
5.4.2問(wèn)題分析70
5.4.3算法實(shí)現(xiàn)70
5.5最小生成樹問(wèn)題72
5.5.1問(wèn)題描述72
5.5.2Prim算法原理72
5.5.3Prim算法實(shí)現(xiàn)72
5.5.4Kruskal算法原理74
5.5.5Kruskal算法實(shí)現(xiàn)75
5.6單源最短路徑問(wèn)題77
5.6.1問(wèn)題描述77
5.6.2Dijkstra算法原理77
5.6.3Dijkstra算法實(shí)現(xiàn)78
5.7本章習(xí)題80
第6章深度優(yōu)先搜索/81
6.1樹的搜索81
6.1.1解空間、子集樹與排列樹81
6.1.2深度優(yōu)先搜索82
6.1.30��1背包問(wèn)題的回溯算法84
6.1.4n皇后問(wèn)題86
6.1.5旅行推銷員問(wèn)題88
6.1.6最大團(tuán)問(wèn)題90
6.1.7圖著色問(wèn)題91
6.1.8連續(xù)郵資問(wèn)題92
6.2圖的搜索94
6.2.1狼羊過(guò)河問(wèn)題95
6.2.2分油問(wèn)題98
6.3本章習(xí)題100
第7章寬度優(yōu)先搜索/102
7.1寬度優(yōu)先搜索一般形式102
7.1.1基本算法102
7.1.2算法性能103
7.1.3算法設(shè)計(jì)要素104
7.2樹的分支定界法104
7.2.10��1背包問(wèn)題104
7.2.2旅行推銷員問(wèn)題107
7.3圖的分支定界法109
7.3.1狼羊過(guò)河問(wèn)題109
7.3.2分油問(wèn)題112
7.4本章習(xí)題115
第8章近似算法/116
8.1近似算法的概念116
8.20��1背包問(wèn)題的0.5�步�似算法117
8.2.1貪心算法117
8.2.20.5�步�似算法118
8.30��1背包問(wèn)題的(1�拨�)�步�似算法118
8.3.1一種動(dòng)態(tài)規(guī)劃算法118
8.3.2(1�拨�)�步�似算法120
8.4旅行推銷員問(wèn)題的2�步�似算法121
8.5本章習(xí)題124
第9章隨機(jī)算法/126
9.1數(shù)值型隨機(jī)算法126
9.1.1數(shù)值積分隨機(jī)算法126
9.1.2隨機(jī)計(jì)數(shù)器127
9.2蒙特卡洛算法128
9.2.1矩陣乘法驗(yàn)證128
9.2.2質(zhì)數(shù)檢測(cè)129
9.3Las Vegas算法132
9.3.1n皇后問(wèn)題132
9.3.2通用散列算法134
9.4本章習(xí)題135
第10章高級(jí)數(shù)據(jù)結(jié)構(gòu)（一）/136
10.1線段樹136
10.1.1線段樹的應(yīng)用背景136
10.1.2線段樹的結(jié)構(gòu)136
10.1.3線段樹的性質(zhì)137
10.1.4線段樹的基本存儲(chǔ)結(jié)構(gòu)138
10.1.5線段樹的基本操作138
10.1.6線段樹的應(yīng)用舉例140
10.2樹狀數(shù)組142
10.2.1樹狀數(shù)組的應(yīng)用背景142
10.2.2樹狀數(shù)組的定義142
10.2.3樹狀數(shù)組的實(shí)現(xiàn)143
10.2.4樹狀數(shù)組的應(yīng)用143
10.3伸展樹144
10.3.1伸展樹的應(yīng)用背景144
10.3.2伸展樹的定義及特點(diǎn)144
10.3.3伸展樹的主要操作145
10.4Treap151
10.4.1概述151
10.4.2Treap基本操作151
10.4.3Treap的其他操作153
10.4.4總結(jié)155
10.5本章習(xí)題156
第11章高級(jí)數(shù)據(jù)結(jié)構(gòu)（二）/157
11.1塊狀鏈表157
11.1.1塊狀鏈表基本思想157
11.1.2塊狀鏈表基本操作157
11.1.3塊狀鏈表的應(yīng)用162
11.2后綴樹163
11.2.1模式匹配問(wèn)題163
11.2.2后綴樹簡(jiǎn)介163
11.2.3后綴樹定義163
11.2.4后綴樹的構(gòu)建164
11.2.5后綴樹的應(yīng)用166
11.3樹鏈剖分168
11.3.1樹鏈剖分的思想和性質(zhì)168
11.3.2樹鏈剖分的實(shí)現(xiàn)及應(yīng)用169
11.4本章習(xí)題177
參考文獻(xiàn)/178