算法设计与分析PDF电子书下载

第一部分 计算模型 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