目录 1
第1章 预备知识 1
1.1 简介 1
1.2 什么是算法 1
1.3 程序符号 4
1.4 数学符号 5
1.4.1 命题演算 5
1.4.2 集合论 6
1.4.3 整数、实数和区间 7
1.4.4 函数和关系 7
1.4.5 量词 8
1.4.6 累加与累积 9
1.4.7 杂项 10
1.5 证明技巧1——反证法 11
1.6 证明技巧2——数学归纳法 12
1.6.1 数学归纳法的法则 15
1.6.2 不同颜色的马 18
1.6.3 一般化的数学归纳法 19
1.6.4 构造性归纳 22
1.7 一些回顾 24
1.7.1 极限 24
1.7.2 简单级数 26
1.7.3 基本组合 30
1.7.4 概率基础 32
1.8 习题 38
1.9 参考与深入阅读 43
2.2 问题和实例 45
2.1 简介 45
第2章 基本算法 45
2.3 算法的效率 46
2.4 平均和最坏情况分析 48
2.5 什么是基本运算？ 50
2.6 为什么寻求效率？ 52
2.7 一些例子 53
2.7.1 计算行列式的值 53
2.7.2 排序 53
2.7.3 大整数的乘法 55
2.7.4 计算最大公约数 55
2.7.5 计算斐波纳契序列 56
2.7.6 傅立叶变换 57
2.9 习题 58
2.8 什么时候算法是确定的？ 58
2.10 参考与深入阅读 61
第3章 渐近记法 62
3.1 引言 62
3.2 同阶记法 62
3.3 其他渐近记法 67
3.3.1 Ω记法 67
3.3.2 Θ记法 68
3.4 条件渐近记法 69
3.5 具有多个参数的渐近记法 71
3.6 渐近记法的操作 71
3.7 习题 72
3.8 参考与深入阅读 75
4.2.1 先后顺序 76
4.2 分析控制结构 76
4.2.2 For循环 76
第4章 算法分析 76
4.1 引言 76
4.2.3 递调用 78
4.2.4 while和repeat循环 79
4.3 使用标称 80
4.4 补充例子 82
4.4.1 选择排序 82
4.4.2 插入排序 83
4.4.3 欧儿里德算法 83
4.4.4 汉诺塔 85
4.4.5 计算行列式的值 86
4.5 平均情况分析 86
4.6 分期分析 87
4.6.1 势函数 88
4.7.1 推测 90
4.6.2 账户戏法 90
4.7 求解递归式 90
4.7.2 齐次递归式 92
4.7.3 非齐次递归式 96
4.7.4 变量变换 100
4.7.5 范围转换 105
4.7.6 渐近递归式 106
4.8 习题 107
4.9 参考与深入阅读 113
第5章 一些数据结构 114
5.1 数组、栈和队列 114
5.2 记录和指针 116
5.3 链表 117
5.4 图 118
5.5 树 119
5.6 关联表 124
5.7 堆 126
5.8 二项堆 132
5.9 不相交集结构 136
5.10 习题 141
5.11 参考与深入阅读 144
第6章 贪婪算法 146
6.1 找零钱（1） 146
6.2 贪婪算法的一般特性 147
6.3 图：最小生成树 148
6.3.1 Kruskal算法 150
6.3.2 Prim算法 152
6.4 图：最短路径 154
6.5 背包问题（1） 157
6.6.1 最小化时间 160
6.6 日程安排 160
6.6.2 有期限的日程安排 162
6.7 习题 168
6.8 参考与深入阅读 170
第7章 分治算法 171
7.1 简介：大整数乘法 171
7.2 通用模板 174
7.3 二分搜索 176
7.4 排序 178
7.4.1 归并排序 178
7.4.2 快速排序 180
7.5 查找中值 184
7.6 矩阵乘法 188
7.7 求幂 189
7.8 综合：密码学简介 192
7.9 习题 194
7.10 参考与深入阅读 200
第8章 动态规划 202
8.1 两个简单的例子 202
8.1.1 计算二项式系数 202
8.1.2 系列赛 203
8.2 找零钱（2） 205
8.3 最优性原则 207
8.4 背包问题（2） 208
8.5 最短路径 209
8.6 链式矩阵乘法 211
8.7 使用递归 214
8.8 存储函数 216
8.9 习题 217
8.10 参考与深入阅读 221
9.1 图和游戏：简介 223
第9章 搜索图 223
9.2 遍历树 228
9.2.1 预处理 228
9.3 深度优先搜索：无向图 230
9.3.1 关节点 232
9.4 深度优先搜索：有向图 233
9.4.1 无环图：拓扑排序 234
9.5 广度优先搜索 236
9.6 回溯法 239
9.6.1 背包问题（3） 240
9.6.2 八皇后问题 242
9.6.3 通用模板 244
9.7 分支界限 244
9.7.1 分配任务问题 245
9.8 极小化原则 248
9.7.2 背包问题（4） 248
9.7.3 一般考虑 248
9.9 习题 251
9.10 参考与深入阅读 256
第10章 概率算法 257
10.1 简介 257
10.2 概率不意味着不确定 258
10.3 预期与平均时间 259
10.4 生成伪随机数 259
10.5 数值概率算法 261
10.5.1 Buffon的针 261
10.5.2 数值积分 264
10.5.3 概率计数 265
10.6.1 验证矩阵乘法 267
10.6 Monte Carlo算法 267
10.6.2 素数性测试 269
10.6.3 一个数可能是素数吗？ 272
10.6.4 随机优势的扩大 274
10.7 Las Vegas算法 276
10.7.1 重访八皇后问题 278
10.7.2 概率选择与排序 281
10.7.3 通用散列 282
10.7.4 大整数分解因数 284
10.8 习题 287
10.9 参考与深入阅读 293
第11章 并行算法 295
11.1 并行计算的模型 295
11.2 一些基本的技术 297
11.2.1 计算完全二叉树 297
11.2.2 指针倍增 298
11.3 工作量与效率 301
11.4 图论的两个例子 303
11.4.1 最短路径 303
11.4.2 连通分量 304
11.5 表达式的并行求值 308
11.6 并行排序网络 312
11.6.1 0-1原理 313
11.6.2 并行合并网络 314
11.6.3 改进的排序网络 315
11.7 并行排序 316
11.7.1 预备工作 316
11.7.2 核心思想 317
11.7.3 算法 317
11.7.4 细节概述 318
11.8 EREW和CRCW p-ram的一些注意点 319
11.9 分布式计算 320
11.10 习题 321
11.11 参考与深入阅读 323
第12章 计算复杂性 324
12.1 引言：一个简单的例子 324
12.2 信息-理论论证 325
12.2.1 排序的复杂性 327
12.2.2 复杂性对算法设计的帮助 330
12.3 对手论证 331
12.3.1 查找数组的最大项 332
12.3.2 测试图的连通性 333
12.3.3 中值再考察 333
12.4 线性归约 335
12.4.1 形式定义 337
12.4.2 矩阵问题中的归约 338
12.4.3 最短路径问题中的归约 342
12.5 NP完全性介绍 344
12.5.1 P和NP类 345
1 2.5.2 多项式归约 348
12.5.3 NP完全性问题 351
12.5.4 一些NP完全性证明 353
12.5.5 NP难问题 356
12.5.6 非确定性算法 357
12.6 复杂性类纵览 359
12.7 习题 362
12.8 参考与深入阅读 366
第13章 启发式和近似算法 369
13.1 启发式算法 369
13.1.1 图着色 369
13.1.2 旅行商 371
13.2 近似算法 372
13.2.1 度量旅行商 372
13.2.2 背包问题（5） 374
13.2.3 装箱问题 375
13.3 NP难近似问题 377
13.3.1 绝对难近似问题 378
13.3.2 相对难近似问题 379
13.4 相同，惟一不同 380
13.5 近似模式 383
13.5.1 重访装箱问题 383
13.5.2 背包问题（6） 384
13.6 习题 386
13.7 参考与深入阅读 389
参考文献 390