新编实用算法分析与程序设计PDF电子书下载

第1章 绪论 1

1.1算法的基本定义 1

1.2算法的空间复杂度 2

1.2.1压缩存储技术 2

1.2.2原地工作 3

1.3算法的时间复杂度 3

1.3.1基本运算 4

1.3.2输入规模 4

1.3.3输入情况 5

1.3.4时间复杂度的阶 6

1.4优化时间效率的方法 8

1.4.1编程实现算法时注意细节优化 8

1.4.2寻找解题思路时尽可能考虑最优性 13

1.5实际生活中常见的算法问题 16

第2章 排序、顺序统计与解题的基本策略 18

2.1计数排序与贪心策略 19

2.1.1计数排序 19

2.1.2贪心策略 22

2.2“二分”思想与快速排序 30

2.2.1分类和分治思想 30

2.2.2快速排序采用二分法 30

2.2.3快速排序和二分法在顺序统计问题上的应用 32

2.3堆排序的思想与应用 36

2.3.1在调整中保持堆性质 37

2.3.2建堆 37

2.3.3堆排序 38

2.4数据有序化 46

2.4.1预处理阶段的数据有序化 46

2.4.2实时处理阶段的数据有序化 47

习题 51

第3章 初等数论的有关算法 54

3.1计算a和b最大公约数的欧几里得公式gcd（a，b） 54

3.2计算N的最大互质数 55

3.3欧几里得公式推广：计算最大公约数的线性组合 56

3.4计算同余方程ax？b（modn）（n＞0） 56

3.5求解同余式组 61

3.6解不定方程ax+by？c 68

3.7初等数论知识的应用 75

3.7.1运用反复平方法求数的幂模n 75

3.7.2素数的测试 81

3.7.3整数的因子分解 82

习题 83

第4章 计算几何学的有关算法 86

4.1线段的性质 86

4.2计算两条相交线段的交点 94

4.3判断任意一组线段中是否存在相交情况 95

4.4计算线段p1p2的中垂线方程 97

4.5计算凸多边形的重心位置和面积 101

4.6寻找最近点对 102

4.7计算包含平面所有点的二维凸包 105

4.8将凸包问题由二维拓展至三维 110

4.8.1计算三维凸包体积的基本思想 110

4.8.2计算由3个空间点组成的劈面三棱柱的体积V（R（△i）） 111

4.8.3计算包含点的三维凸包体积 112

4.9计算几何类问题的类型和应对的基本方法 114

习题 120

第5章 搜索的有关算法 124

5.1枚举法 124

5.2宽度优先搜索 129

5.2.1宽度优先搜索的定义 129

5.2.2宽度优先搜索的应用 130

5.3深度优先搜索与回溯法 134

5.3.1深度优先搜索 134

5.3.2回溯法—采用纵深搜索的策略构建与处理隐式图 139

5.4搜索的剪枝优化 150

5.5二分搜索 167

5.6参数搜索 173

习题 183

第6章 图论的有关算法 187

6.1计算图的传递闭包 187

6.2最小生成树的算法及其应用 193

6.2.1计算最小生成树的基本思路 193

6.2.2计算最小生成树的两种算法 195

6.2.3最小生成树的应用实例 202

6.3最短路径的算法及其应用 209

6.3.1最短路径计算的基本原理 209

6.3.2计算最短路径的常用算法 212

6.4二分图的匹配及其应用 223

6.4.1二分图和匹配的基本概念 224

6.4.2怎样判别二分图 225

6.4.3怎样计算二分图的最大匹配 226

6.4.4二分图的最小覆盖问题 231

6.4.5二分图的最佳匹配问题 235

6.5网络流图的思想和应用 246

6.5.1计算网络流量的基本思想 247

6.5.2按层次计算最大流的Dinic算法 250

6.5.3计算网络流量的应用实例 253

6.5.4网络增加多源多汇和容量下界因素后的流量计算问题 263

6.5.5网络增加费用因素后的流量计算问题 271

习题 283

第7章 讨论动态规划 286

7.1动态规划的基本思想 286

7.2动态规划的计算步骤 286

7.3动态规划的优化策略 294

习题 324

参考文献 328