第1章 导论 1
1.1 什么是算法 1
1.2 算法规范 3
1.2.1 导论 3
1.2.2 递归算法 5
1.3 性能分析 8
1.3.1 空间复杂度 8
1.3.2 时间复杂度 9
1.3.3 平摊复杂度 16
1.3.4 渐进符号（O，Ω，Θ） 23
1.3.5 实际复杂度 29
1.3.6 性能测量 31
1.4 概率算法 39
1.4.1 概率论基础 39
1.4.2 随机算法：正规描述 42
1.4.3 确认重复元素 43
1.4.4 素数测试 44
1.4.5 优缺点 47
1.5 参考文献及阅读 49
第2章 数据结构基础 50
2.1 栈与队列 50
2.2 树 56
2.2.1 术语 57
2.2.2 二叉树 58
2.3 字典 60
2.3.1 二叉搜索树 61
2.4 优先队列 66
2.4.1 堆 67
2.4.2 堆排序 71
2.5 集合与不相交集合的并集 73
2.5.1 导论 73
2.5.2 求并集及查找操作 74
2.6 图 80
2.6.1 导论 80
2.6.2 定义 81
2.6.3 图的表示 83
2.7 参考文献及阅读 89
第3章 分治策略 90
3.1 一般方法 90
3.2 残缺棋盘 93
3.3 二分搜索 96
3.4 找最大值和最小值 101
3.5 合并排序 105
3.6 快速排序 111
3.6.1 性能测量 114
3.6.2 随机排序算法 115
3.7 选择 117
3.7.1 最差情况下的最优算法 120
3.7.2 Select2的实现 122
3.8 矩阵相乘 127
3.9 凸包 130
3.9.1 几种几何基本 130
3.9.2 QuickHull算法 131
3.9.3 Graham扫描 132
3.9.4 O（nlogn）的分治算法 134
3.10 参考文献及阅读 136
3.11 附加习题 137
第4章 贪心法 139
4.1 一般方法 139
4.2 集装箱装船 142
4.3 背包问题 144
4.4 树节点分裂 147
4.5 有期限的工作序列化 150
4.6 最小生成树 156
4.6.1 Prim算法 157
4.6.2 Kruskal算法 159
4.6.3 最优的随机算法（＊） 162
4.7 磁带最优存储 164
4.8 最优合并模式 168
4.9 单源最短路径 172
4.10 参考文献及阅读 177
4.11 附加习题 178
第5章 动态规划 180
5.1 一般方法 180
5.2 多段图 183
5.3 每对顶点间最短路径 187
5.4 单源最短路径：一般权重 190
5.5 最优二叉搜索树（＊） 193
5.6 串编辑 198
5.7 0/1背包 201
5.8 可靠性设计 207
5.9 旅行商问题 209
5.10 流水车间调度 211
5.11 参考文献及阅读 215
5.12 附加习题 215
第6章 基本遍历及搜索技术 219
6.1 二叉树的遍历及搜索 219
6.2 图的遍历及搜索 222
6.2.1 广度优先搜索及遍历 223
6.2.2 深度优先搜索及遍历 225
6.3 连通分支及生成树 226
6.4 双连通分支 228
6.5 参考文献及阅读 234
第7章 回溯 235
7.1 一般方法 235
7.2 八皇后问题 243
7.3 子集求和 246
7.4 图着色 248
7.5 哈密尔顿回路 251
7.6 背包问题 253
7.7 参考文献及阅读 256
7.8 附加习题 257
第8章 分支定界 260
8.1 方法 260
8.1.1 最少代价（LC）搜索 260
8.1.2 15拼图：一个例子 262
8.1.3 最少代价搜索的控制抽象 265
8.1.4 定界 266
8.1.5 FIFO分支定界 268
8.1.6 LC分支定界 268
8.2 0/1背包问题 269
8.2.1 LC分支定界解法 270
8.2.2 FIFO分支定界解法 272
8.3 旅行商问题（＊） 275
8.4 效率 280
8.5 参考文献及阅读 282
第9章 代数问题 283
9.1 一般方法 283
9.2 求值与插值 284
9.3 快速傅里叶变换（FFT） 292
9.3.1 In-place版本的快速傅里叶变换 296
9.3.2 继续思考 298
9.4 模算术 299
9.5 更快的求值和插值 305
9.6 参考文献及阅读 310
第10章 下界理论 312
10.1 比较树 312
10.1.1 有序搜索 313
10.1.2 排序 314
10.1.3 选择 316
10.2 预言及对手论证 318
10.2.1 合并 318
10.2.2 最大和次大 319
10.2.3 状态空间法 320
10.2.4 选择 321
10.3 规约求下界 322
10.3.1 找凸包 323
10.3.2 不相交集合问题 324
10.3.3 在线中位数查找 324
10.3.4 三角形矩阵相乘 325
10.3.5 下三角形矩阵求逆 326
10.3.6 计算传递闭包 327
10.4 代数问题中的技巧（＊） 329
10.5 参考文献及阅读 335
第11章 NP难及NP完全问题 336
11.1 基本概念 336
11.1.1 非确定算法 336
11.1.2 NP难及NP完全 342
11.2 Cook定理（＊） 344
11.3 NP难的图问题 350
11.3.1 团判定问题（CDP） 350
11.3.2 点覆盖判定问题（NCDP） 351
11.3.3 色数判定问题（CNDP） 352
11.3.4 有向图哈密尔顿回路问题（DHC）（＊） 353
11.3.5 旅行商判定问题（TSP） 355
11.3.6 AND/OR图判定问题（AOG） 355
11.4 NP难的调度问题 360
11.4.1 调度相同处理器 360
11.4.2 流水车间调度 362
11.4.3 作业车间调度 363
11.5 NP难的代码生成问题 364
11.5.1 有公共子表达式的代码生成 366
11.5.2 实现并行赋值指令 369
11.6 简化的NP难问题 370
11.7 参考文献及阅读 372
11.8 附加习题 373
第12章 近似算法 375
12.1 导论 375
12.2 绝对近似 377
12.2.1 平面图着色 377
12.2.2 最大程序存储问题 378
12.2.3 NP难的绝对近似 379
12.3 ε近似 380
12.3.1 调度独立任务 380
12.3.2 装箱 382
12.3.3 NP难的ε近似问题 384
12.4 多项式时间近似方案 388
12.4.1 调度独立任务 388
12.4.2 0/1背包 389
12.5 完全多项式时间近似方案 393
12.5.1 舍入 394
12.5.2 区间划分 397
12.5.3 间隔 397
12.6 概率上好的近似方案（＊） 400
12.7 参考文献及阅读 402
12.8 附加习题 402
第13章 PRAM算法 406
13.1 介绍 406
13.2 计算模型 408
13.3 基本技巧和算法 412
13.3.1 前缀计算 413
13.3.2 表排列 414
13.4 选取 420
13.4.1 使用n2个处理器选取最大元 420
13.4.2 使用n个处理器选取最大元 421
13.4.3 整数范围内的最大元 421
13.4.4 使用n2个处理进行一般性选择 423
13.4.5 工作最优的随机化选择算法（＊） 423
13.5 归并 426
13.5.1 对数时间的算法 426
13.5.2 奇偶归并 426
13.5.3 工作最优的算法 428
13.5.4 一个运行时间为O（log log m）的算法 429
13.6 排序 430
13.6.1 奇偶归并排序 430
13.6.2 一个可供选择的随机化算法 431
13.6.3 Preparata算法 431
13.6.4 Reischuk随机化算法（＊） 432
13.7 图问题 434
13.7.1 传递闭包的另一种计算方法 436
13.7.2 全点对的最小路径问题 436
13.8 凸包计算 437
13.9 下界 439
13.9.1 排序的平均运行时间下界 440
13.9.2 寻找最大元 441
13.10 参考文献及阅读 442
13.11 附加习题 443
第14章 网格算法 445
14.1 计算模型 445
14.2 数据包路由 446
14.2.1 线性数组中的数据包路由 447
14.2.2 网格上PPR问题的贪心算法 450
14.2.3 使用小队列的随机化算法 450
14.3 基本算法 452
14.3.1 广播 453
14.3.2 前缀计算 454
14.3.3 数据聚集 455
14.3.4 稀疏列举排序 456
14.4 选取 459
14.4.1 n=p′情形下的随机化算法（＊） 459
14.4.2 n>p情形下的随机化算法（＊） 460
14.4.3 n>p情形下的确定性算法 460
14.5 归并 463
14.5.1 通过秩实现线性数组上的归并 463
14.5.2 线性数组上的奇偶归并 464
14.5.3 网格上的奇偶归并 465
14.6 排序 466
14.6.1 线性数组上的排序 466
14.6.2 网格上的排序 467
14.7 图问题 470
14.7.1 n×n网格上的传递闭包算法 471
14.7.2 全点对最短路径算法 472
14.8 凸包计算 472
14.9 参考文献及阅读 475
14.10 附加习题 477
第15章 超立方算法 479
15.1 计算模型 479
15.1.1 超立方 479
15.1.2 蝴蝶网络 480
15.1.3 其他网络的嵌入 482
15.2 偏转置路由 484
15.2.1 贪心算法 484
15.2.2 随机化算法 485
15.3 基本算法 487
15.3.1 广播 487
15.3.2 前缀计算 488
15.3.3 数据聚集 489
15.3.4 稀疏列举排序 491
15.4 选取 492
15.4.1 n=p情形下的随机化算法（＊） 492
15.4.2 n>p情形下的随机化选取算法（＊） 493
15.4.3 n>p情形下的确定性算法 493
15.5 归并 495
15.5.1 奇偶归并 495
15.5.2 双调归并 496
15.6 排序 498
15.6.1 奇偶归并排序 498
15.6.2 双调排序 498
15.7 图问题 499
15.8 凸包计算 500
15.9 参考文献及阅读 501
15.10 附加习题 502