第一部分 基本概念和算法导引 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 多项式求值（Horner规则） 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.3 k带图灵机和时间复杂性 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 Dimc算法 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.3 Voronoi图解的应用 304
19.4 最远点Voronoi图解 306
19.5 最远点Voronoi图解的应用 308
19.6 练习 309
19.7 参考注释 310
参考文献 311