目录 1
出版者的话 1
专家指导委员会 1
译者序 1
前言 1
第1章 导论 1
1.1 什么是算法 1
1.2 算法规范 3
1.2.1 引言 3
1.2.2 递归算法 4
2.4.1 堆 5
1.3.1 空间复杂度 7
1.3 性能分析 7
1.3.2 时间复杂度 8
1.3.3 渐近符号（O、Ω、？） 14
1.3.4 实际复杂度 19
1.3.5 性能度量 21
1.4 随机算法 28
1.4.1 概率论基础 28
1.4.2 随机算法：非形式化的描述 30
1.4.3 识别重复元素 31
1.4.4 素数测试 33
1.4.5 优点与缺点 35
1.5 参考文献和读物 36
第2章 基本数据结构 39
2.1 栈和队列 39
2.2 树 44
2.2.1 术语 44
2.2.2 二叉树 45
2.3 字典 47
2.3.1 二叉查找树 48
2.3.2 代价分摊 52
2.4 优先队列 53
2.4.2 堆排序 58
2.5 集合和不相交集合的并 59
2.5.1 概述 59
2.5.2 并和查找操作 60
2.6 图 66
2.6.1 概述 66
2.6.2 定义 66
2.6.3 图的表示方法 69
2.7 参考文献和读物 73
第3章 分治算法 75
3.1 一般方法 75
3.2 二叉查找 77
3.3 查找最大值和最小值 82
3.4 归并排序 85
3.5 快速排序 90
3.5.1 性能度量 93
3.5.2 随机排序算法 94
3.6 选择 96
3.6.1 最坏情况下的最优算法 99
3.6.2 Select2的实现 101
3.7 Strassen矩阵乘法 104
3.8 凸包 107
3.8.1 几种原始几何方法 108
3.8.2 QuickHull算法 108
3.8.3 Graham扫描算法 109
3.8.4 一个O（nlogn）的分治算法 111
3.10 附加习题 113
3.9 参考文献和读物 113
第4章 贪心算法 115
4.1 一般方法 115
4.2 背包问题 116
4.3 树节点分割 118
4.4 带有期限的作业顺序问题 121
4.5 最小代价生成树 126
4.5.1 Prim算法 127
4.5.2 Kruskal算法 129
4.5.3 一个最优随机算法（＊） 131
4.6 磁带的最优存储 133
4.7 最优归并模式 136
4.8 单源最短路径 140
4.9 参考文献和读物 144
4.10 附加习题 145
第5章 动态规划 147
5.1 一般方法 147
5.2 多部图 149
5.3 每一对顶点之间的最短路径 153
5.4 单源最短路径：普通权值 156
5.5 最优二叉查找树（＊） 158
5.6 串编辑 163
5.7 0/1背包 165
5.8 可靠性设计 170
5.9 旅行商问题 172
5.10 流水作业调度 174
5.11 参考文献和读物 177
5.12 附加习题 178
第6章 基本的查找和遍历技术 181
6.1 二叉树算法 181
6.2 图算法 184
6.2.1 广度优先搜索和遍历 184
6.2.2 深度优先搜索和遍历 186
6.3 连通分支和生成树 187
6.4 双连通分支和DFS算法 189
6.5 参考文献和读物 193
第7章 回溯 195
7.1 一般方法 195
7.2 8皇后问题 202
7.3 子集求和问题 204
7.4 图的着色 206
7.5 哈密顿回路 209
7.6 背包问题 210
7.7 参考文献和读物 213
7.8 附加习题 214
第8章 分支限界法 217
8.1 一般方法 217
8.1.1 最小代价查找 218
8.1.2 15拼板：一个例子 219
8.1.3 LC查找的控制抽象 221
8.1.4 限界 223
8.1.5 FIFO分支限界法 224
8.1.6 LC分支限界法 225
8.2 0/1背包问题 226
8.2.1 LC分支限界法求解 226
8.2.2 FIFO分支限界法求解 228
8.3 旅行商问题（＊） 230
8.4 效率因素 235
8.5 参考文献和读物 237
9.1 一般方法 239
第9章 代数问题 239
9.2 计算和插值 240
9.3 快速傅里叶变换 246
9.3.1 FFT的原地版本 250
9.3.2 一些保留问题 252
9.4 模运算 252
9.5 更快的计算和插值 257
9.6 参考文献和读物 262
第10章 下界理论 263
10.1 比较树 263
10.1.1 有序查找 264
10.1.2 排序 264
10.1.3 选择 268
10.2 喻示和对立论 269
10.2.1 归并 269
10.2.2 最大和次大 270
10.2.3 状态空间方法 271
10.2.4 选择 272
10.3 通过规约求下界 274
10.3.1 寻找凸包 274
10.3.2 不相交集合问题 275
10.3.3 即时中值查找 275
10.3.4 三角矩阵相乘 276
10.3.5 下三角矩阵求逆 277
10.3.6 计算传递闭包 278
10.4 解决代数问题的技术（＊） 280
10.5 参考文献和读物 286
第11章 NP难与NP完全问题 289
11.1 基本概念 289
11.1.1 非确定性算法 289
11.1.2 NP难和NP完全类 294
11.2 Cook定理（＊） 296
11.3 NP难的图问题 301
11.3.1 团判定问题 301
11.3.2 节点覆盖判定问题 302
11.3.3 色数判定问题 303
11.3.4 有向哈密顿回路（＊） 304
11.3.5 旅行商判定问题 306
11.3.6 与／或图判定问题 306
11.4 NP难的调度问题 310
11.4.1 调度相同的处理器 310
11.4.2 流水作业调度 311
11.4.3 作业安排调度 312
11.5 NP难的代码生成问题 314
11.5.1 带有公共子表达式的代码生成 315
11.5.2 实现并行赋值指令 318
11.6 一些简化的NP难问题 319
11.7 参考文献和读物 321
11.8 附加习题 322
第12章 近似算法 325
12.1 概述 325
12.2.2 最多程序存储问题 327
12.2 绝对近似 327
12.2.1 平面图着色 327
12.2.3 NP难的绝对近似 328
12.3 ε近似 330
12.3.1 独立任务的调度 330
12.3.2 装箱问题 332
12.3.3 NP难的ε近似问题 333
12.4 多项式时间近似方案 337
12.4.1 独立任务的调度 337
12.4.2 0/1背包 338
12.5 完全多项式时间近似方案 341
12.5.1 舍入法 342
12.5.2 区间划分法 345
12.5.3 分割法 346
12.6 概率上的好算法（＊） 349
12.7 参考文献和读物 350
12.8 附加习题 351
13.1 概述 355
第13章 PRAM算法 355
13.2 计算模型 357
13.3 基本技术和算法 361
13.3.1 前缀计算 361
13.3.2 表排序 362
13.4 选择 367
13.4.1 使用n2个处理器选择最大值 367
13.4.2 使用n个处理器选择最大值 368
13.4.3 在整数中选择最大值 369
13.4.4 使用n2个处理器的一般选择问题 370
13.4.5 一个工作最优的随机算法（＊） 370
13.5 归并 372
13.5.1 对数时间算法 373
13.5.2 奇偶归并 373
13.5.3 工作最优的算法 374
13.5.4 O（log logm）时间算法 375
13.6 排序 376
13.6.1 奇偶归并排序 377
13.6.2 随机选择算法 377
13.6.3 Preparata算法 378
13.6.4 Reischuk随机算法（＊） 379
13.7 图问题 381
13.7.1 计算传递闭包的另一种算法 382
13.7.2 每一对顶点之间的最短路径 383
13.8 计算凸包 383
13.9 下界 385
13.9.1 平均情况下排序的下界 386
13.9.2 寻找最大值 387
13.10 参考文献和读物 388
13.11 附加习题 389
第14章 网格算法 391
14.1 计算模型 391
14.2 分组路由 392
14.2.1 线性阵列中的分组路由 393
14.2.2 网格上PPR的贪心算法 394
14.2.3 具有小队列的随机算法 395
14.3 基本算法 397
14.3.1 广播 398
14.3.2 前缀计算 398
14.3.3 数据集中 400
14.3.4 稀疏枚举排序 401
14.4 选择 403
14.4.1 n=p（＊）时的随机算法 403
14.4.2 n>p（＊）时的随机选择 404
14.4.3 n>p时的确定性算法 404
14.5 归并 407
14.5.1 在线性阵列上的顺序号归并 407
14.5.2 线性阵列上的奇偶归并 408
14.5.3 在网格上的奇偶归并 408
14.6 排序 409
14.6.2 在网格上的排序 410
14.6.1 在线性阵列上的排序 410
14.7 图问题 413
14.7.1 传递闭包的n×n网格算法 414
14.7.2 每一对顶点之间的最短路径 415
14.8 计算凸包 416
14.9 参考文献和读物 418
14.10 附加习题 420
第15章 超立方体算法 423
15.1 计算模型 423
15.1.1 超立方体 423
15.1.2 蝶形网络 424
15.1.3 其他网络的嵌入 425
15.2 PPR路由 427
15.2.1 贪心算法 427
15.2.2 随机算法 428
15.3.1 广播 430
15.3.2 前缀计算 430
15.3 基本算法 430
15.3.3 数据集中 431
15.3.4 稀疏枚举排序 433
15.4 选择 434
15.4.1 n=p（＊）时的随机算法 434
15.4.2 n>p（＊）时的随机选择 435
15.4.3 n>p时的确定性算法 435
15.5.1 奇偶归并 437
15.5 归并 437
15.5.2 双调谐归并 438
15.6 排序 439
15.6.1 奇偶归并排序 439
15.6.2 双调谐排序 439
15.7 图问题 440
15.8 计算凸包 441
15.9 参考文献和读物 442
15.10 附加习题 443
索引 445