第一部分 基本概念和算法导引 1
第1章 算法分析基本概念 2
1.1引言 2
1.2历史背景 2
1.3二分搜索 3
1.4合并两个已排序的表 6
1.5选择排序 7
1.6插入排序 8
1.7自底向上合并排序 9
1.8时间复杂性 12
1.9空间复杂性 19
1.10最优算法 20
1.11如何估计算法运行时间 21
1.12最坏情况和平均情况的分析 26
1.13平摊分析 29
1.14输入大小和问题实例 31
1.15练习 32
1.16参考注释 38
第2章 数学预备知识 39
2.1集合、关系和函数 39
2.2证明方法 41
2.3对数 44
2.4底函数和顶函数 45
2.5阶乘和二项式系数 45
2.6鸽巢原理 48
2.7和式 48
2.8递推关系 52
2.9练习 63
第3章 数据结构 67
3.1引言 67
3.2链表 67
3.3图 68
3.4树 69
3.5根树 70
3.6二叉树 71
3.7练习 72
3.8参考注释 73
第4章 堆和不相交集数据结构 74
4.1引言 74
4.2堆 74
4.3不相交集数据结构 80
4.4练习 85
4.5参考注释 88
第二部分 基于递归的技术 89
第5章 归纳法 90
5.1引言 90
5.2两个简单的例子 90
5.3基数排序 92
5.4整数幂 93
5.5多项式求值（Homer规则） 94
5.6生成排列 95
5.7寻找多数元素 98
5.8练习 99
5.9参考注释 101
第6章 分治 102
6.1引言 102
6.2二分搜索 103
6.3合并排序 105
6.4分治范式 107
6.5寻找中项和第k小元素 109
6.6快速排序 112
6.7大整数乘法 118
6.8矩阵乘法 119
6.9最近点对问题 121
6.10练习 124
6.11参考注释 128
第7章 动态规划 129
7.1引言 129
7.2最长公共子序列问题 130
7.3矩阵链相乘 132
7.4动态规划范式 136
7.5所有点对的最短路径问题 136
7.6背包问题 138
7.7练习 140
7.8参考注释 144
第三部分 最先割技术 145
第8章 贪心算法 146
8.1引言 146
8.2最短路径问题 146
8.3最小耗费生成树（Kruskal算法） 151
8.4最小耗费生成树（Prim算法） 153
8.5文件压缩 157
8.6练习 159
8.7参考注释 161
第9章 图的遍历 162
9.1引言 162
9.2深度优先搜索 162
9.3深度优先搜索的应用 165
9.4广度优先搜索 169
9.5广度优先搜索的应用 170
9.6练习 170
9.7参考注释 172
第四部分 问题的复杂性 173
第10章 NP完全问题 174
10.1引言 174
10.2 P类 176
10.3 NP类 176
10.4 NP完全间题 177
10.5 co-NP类 182
10.6 NPI类 183
10.7四种类之间的关系 184
10.8练习 184
10.9参考注释 186
第11章 计算复杂性引论 187
11.1引言 187
11.2计算模型：图灵机 187
11.3k带图灵机和时间复杂性 187
11.4离线图灵机和空间复杂性 189
11.5带压缩和线性增速 191
11.6复杂性类之间的关系 191
11.7归约 196
11.8完全性 198
11.9多项式时间层次 203
11.10练习 205
11.11参考注释 208
第12章 下界 209
12.1引言 209
12.2平凡下界 209
12.3决策树模型 209
12.4代数决策树模型 211
12.5线性时间归约 213
12.6练习 214
12.7参考注释 216
第五部分 克服困难性 217
第13章 回溯法 218
13.1引言 218
13.2 3着色问题 218
13.3 8皇后问题 221
13.4一般回溯方法 223
13.5分支限界法 225
13.6练习 227
13.7参考注释 228
第14章 随机算法 229
14.1引言 229
14.2 Las Vegas和Monte Carlo算法 229
14.3随机化快速排序 230
14.4随机化的选择算法 231
14.5测试串的相等性 232
14.6模式匹配 234
14.7随机取样 235
14.8素数性测试 237
14.9练习 241
14.10参考注释 242
第15章 近似算法 244
15.1引言 244
15.2基本定义 244
15.3差界 245
15.4相对性能界 246
15.5多项式近似方案 250
15.6完全多项式近似方案 253
15.7练习 255
15.8参考注释 257
第六部分 域指定问题的迭代改进 259
第16章 网络流 260
16.1引言 260
16.2预备知识 260
16.3 Ford-Fulkerson方法 262
16.4最大容量增值 263
16.5最短路径增值 264
16.6 Dinic算法 266
16.7 MPM算法 269
16.8练习 270
16.9参考注释 271
第17章 匹配 272
17.1引言 272
17.2预备知识 272
17.3网络流方法 274
17.4二分图的匈牙利树方法 274
17.5一般图中的最大匹配 276
17.6二分图的O（n2.5）算法 281
17.7练习 284
17.8参考注释 286
第七部分 计算几何技术 287
第18章 几何扫描 288
18.1引言 288
18.2几何预备知识 289
18.3计算线段的交点 290
18.4凸包问题 292
18.5计算点集的直径 295
18.6练习 297
18.7参考注释 299
第19章 Voronoi图解 300
19.1引言 300
19.2最近点Voronoi图解 300
19.3Voronoi图解的应用 304
19.4最远点Voronoi图解 306
19.5最远点Voronoi图解的应用 308
19.6练习 309
19.7参考注释 310
参考文献 311