计算机算法PDF电子书下载

第1章 绪论 1

1.1 算法的时间复杂性 2

1.2 算法的空间复杂性 5

1.3 两个算法的分析实例 5

1.4 算法设计技术 7

1.4.1 分治方法 7

1.4.2 回溯法 9

1.4.3 贪心法 11

1.4.4 动态规划法 11

1.4.5 分支限界法 12

1.4.6 递归方程解的展开式 13

习题 14

第2章 排序算法 16

2.1 插入算法 16

2.1.1 直接插入排序 16

2.1.2 折半插入排序 18

2.1.3 希尔排序 19

2.2 选择排序 21

2.2.1 直接选择排序 21

2.2.2 堆排序 22

2.3 交换排序 24

2.3.1 冒泡排序 25

2.3.2 快速排序 25

2.4 归并排序 27

2.5 基数排序 29

2.6 外部排序 32

2.6.1 归并排序 33

2.6.2 多步归并算法 34

2.7 各种内部排序方法的比较讨论 35

习题 36

第3章 查找树 38

3.1 二分查找树 38

3.2 2-3-4树 40

3.3 红黑树 43

3.4 B树 51

习题 56

第4章 图的算法 57

4.1 基本概念 58

4.2 图的表示方法 61

4.3 图的遍历 62

4.4 所有点对之间的最短路径 66

4.5 最小生成树 68

习题 69

第5章 串匹配 70

5.1 简单的字符串匹配算法 70

5.2 Knuth-Morris-Pratt（KMP）字符串匹配 71

5.3 BM算法 75

5.4 RK算法 76

习题 77

第6章 分治算法 78

6.1 二分搜索 78

6.2 求最大元和最小元 80

6.3 大整数乘法 82

6.4 矩阵乘法算法 85

6.5 矩阵乘积的Winograd算法 88

习题 89

第7章 贪心算法 90

7.1 背包问题 91

7.2 带时限的作业排序 94

7.3 单源最短路径问题 96

7.4 最小生成树问题 97

7.5 Dijkstra各点之间最短路径的优化算法 99

习题 102

第8章 回溯法 103

8.1 n皇后问题 103

8.2 图的着色问题 106

8.3 0-1背包问题 109

8.4 哈密顿回路 113

8.5 子集和数 115

习题 118

第9章 动态规划法 119

9.1 最长公共子序列问题 119

9.2 矩阵连乘问题 124

9.3 多阶段决策过程最优化问题 129

9.4 0-1背包问题 130

9.5 流水线调度问题 133

习题 135

第10章 分支限界法 137

10.1 分支限界的策略 137

10.2 0-1背包问题 139

习题 142

第11章 概率算法 143

11.1 随机数 143

11.2 数值概率算法 144

11.3 蒙特卡罗算法 145

11.4 拉斯维加斯算法 147

11.5 舍伍德算法 149

习题 150

第12章 几何问题算法 151

12.1 直线相交问题的算法 151

12.2 点是否包含在多边形内部 153

12.3 求凸包问题 153

习题 157

第13章 NP完全问题 158

13.1 不确定算法和不确定图灵机 158

13.2 NP难度和NP完全问题 160

13.3 COOK定理 161

13.4 几个NP完全问题 162

习题 165

第14章 密码学算法 166

14.1 什么是密码 166

14.2 基本数论 168

14.3 背包公钥密码 169

14.4 RSA算法 170

14.5 数字签名 171

习题 173

第15章 近似算法 174

15.1 任务调度近似算法 174

15.2 顶点覆盖问题近似算法 177

15.3 旅行商问题的近似解 178

15.4 子集和数问题的近似算法 181

习题 183

第16章 并行算法 185

16.1 并行计算机 185

16.2 并行算法的基本概念 189

16.3 并行算法的描述 190

16.4 SIMD-SM上的非线性方程求根同步并行算法 191

16.5 SIMD-SM上的同步并行求和算法 192

16.6 SIMD-CC超立方机器上的同步并行求和算法 194

16.7 MIMD-SM上的异步并行求和算法 195

习题 197

参考文献 198