第一部分 计算模型 2
第1章 抽象的算法设计与分析 2
1.1 RAM模型的引入 2
1.1.1 计算的基本概念 2
1.1.2 计算模型的基本概念 3
1.1.3 RAM模型 4
1.1.4 计算模型的选择：易用性和精确性 6
1.2 抽象算法设计 7
1.2.1 算法问题规约 7
1.2.2 算法正确性证明：数学归纳法 8
1.3 抽象算法分析 10
1.3.1 抽象算法的性能指标 10
1.3.2 最坏情况时间复杂度分析 11
1.3.3 平均情况时间复杂度分析 12
1.4 习题 13
第2章 从算法的视角重新审视数学的概念 16
2.1 数学运算背后的算法操作 16
2.1.1 取整？x」和「x？ 16
2.1.2 对数log n 17
2.1.3 阶乘n！ 18
2.1.4 常见级数求和？f（i） 19
2.1.5 期望E［X］ 20
2.2 函数的渐近增长率 22
2.3 “分治递归”求解 24
2.3.1 替换法 24
2.3.2 分治递归与递归树 25
2.3.3 Master定理 26
2.4 习题 27
第二部分 朴素遍历 32
第3章 线性表的遍历 32
3.1 基于遍历的选择与查找 32
3.2 基于遍历的排序 33
3.2.1 选择排序 34
3.2.2 插入排序 35
3.3 习题 37
第4章 图的深度优先遍历 39
4.1 图和图遍历 39
4.2 有向图的深度优先遍历 40
4.2.1 有向图的深度优先遍历框架 40
4.2.2 有向图的深度优先遍历树 42
4.2.3 活动区间 43
4.3 有向图的深度优先遍历应用 45
4.3.1 拓扑排序 45
4.3.2 关键路径 48
4.3.3 有向图中的强连通片 50
4.4 无向图的深度优先遍历 54
4.4.1 无向图的深度优先遍历树 55
4.4.2 无向图的深度优先遍历框架 56
4.5 无向图的深度优先遍历应用 57
4.5.1 容错连通 57
4.5.2 寻找割点 58
4.5.3 寻找桥 60
4.6 习题 61
第5章 图的广度优先遍历 66
5.1 广度优先遍历 66
5.1.1 广度优先遍历框架 67
5.1.2 有向图的广度优先遍历树 70
5.1.3 无向图的广度优先遍历树 70
5.2 广度优先遍历的应用 72
5.2.1 判断二分图 72
5.2.2 寻找k度子图 73
5.3 习题 74
第三部分 分治策略 78
第6章 排序：从遍历到分治 78
6.1 快速排序 78
6.1.1 插入排序的不足 78
6.1.2 快速排序的改进 79
6.1.3 快速排序的分析 81
6.2 合并排序 84
6.3 基于比较的排序的下界 86
6.3.1 决策树的引入 87
6.3.2 比较排序最坏情况时间复杂度的下界 88
6.3.3 比较排序平均情况时间复杂度的下界 88
6.4 习题 90
第7章 堆的设计与应用 95
7.1 堆的定义 95
7.2 堆的抽象维护 96
7.2.1 堆的修复 96
7.2.2 堆的构建 97
7.3 堆的具体实现 98
7.4 堆的应用 100
7.4.1 堆排序 100
7.4.2 基于堆实现优先队列 100
7.5 习题 101
第8章 线性时间选择 103
8.1 期望线性时间的选择 103
8.1.1 期望线性时间的选择算法设计 103
8.1.2 期望线性时间的选择算法分析 104
8.2 最坏情况线性时间的选择 106
8.2.1 最坏情况线性时间的选择算法设计 106
8.2.2 最坏情况线性时间的选择算法分析 107
8.3 习题 108
第9章 对数时间查找 110
9.1 折半查找 110
9.1.1 经典折半查找 110
9.1.2 折半查找的推广 111
9.2 平衡二叉搜索树 112
9.2.1 二叉搜索树及其平衡性 113
9.2.2 红黑树的定义 114
9.2.3 红黑树的平衡性 115
9.3 习题 116
第四部分 贪心策略 120
第10章 最小生成树 120
10.1 Prim算法 120
10.1.1 Prim算法的正确性 122
10.1.2 Prim算法的实现 125
10.1.3 Prim算法的分析 126
10.2 Kruskal算法 127
10.2.1 Kruskal算法的正确性 128
10.2.2 判断是否成环——基于并查集的实现 129
10.2.3 Kruskal算法的实现与分析 133
10.3 最小生成树贪心构建框架MCE 134
10.3.1 从MCE框架的角度分析Prim算法 135
10.3.2 从MCE框架的角度分析Kruskal算法 136
10.4 习题 137
第11章 给定源点的最短路径 142
11.1 Dijkstra算法 142
11.1.1 Dijkstra算法的设计 142
11.1.2 Dijkstra算法的正确性与性能分析 144
11.2 从Dijkstra算法到贪心遍历框架BestFS 146
11.3 习题 147
第12章 贪心策略的其他应用 151
12.1 相容任务调度问题 151
12.1.1 直觉的尝试 151
12.1.2 基于任务结束时间的贪心算法 152
12.2 Huffman编码 153
12.2.1 可变长度编码 153
12.2.2 最优编码方案的性质 154
12.2.3 贪心的Huffman编码 156
12.3 习题 156
第五部分 动态规划 160
第13章 最短路径 160
13.1 有向无环图上的给定源点最短路径问题 160
13.2 传递闭包问题和Shortcut算法 161
13.3 所有点对最短路径：基于路径长度的递归 163
13.4 Floyd-Warshall算法：基于中继节点范围的递归 164
13.5 习题 166
第14章 动态规划算法 168
14.1 动态规划的动机 168
14.2 动态规划的基本过程 169
14.2.1 基于朴素遍历的递归 170
14.2.2 未作规划的递归 171
14.2.3 采用动态规划的递归 171
14.3 动态规划的应用 174
14.3.1 动态规划的要素 174
14.3.2 编辑距离问题 175
14.3.3 硬币兑换问题 176
14.3.4 最大和连续子序列问题 178
14.3.5 相容任务调度问题 179
14.4 习题 179
第六部分 计算复杂性理论初步 188
第15章 多项式时间归约 188
15.1 问题间的归约 188
15.1.1 优化问题和判定问题 188
15.1.2 问题间归约的定义 189
15.2 多项式时间：解决问题与完成归约 190
15.2.1 多项式时间可解的问题 190
15.2.2 多项式时间归约 191
15.3 习题 192
第16章 NP完全问题的基本概念 193
16.1 NP完全问题的定义 193
16.1.1 NP问题的定义 193
16.1.2 NP难与NP完全问题的定义 194
16.2 NP完全性证明的初步知识 195
16.2.1 一般问题和特例问题 195
16.2.2 等价的问题 196
16.3 习题 197
附录A 数学归纳法 199
附录B 二叉树 200
参考文献 201