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

第一章 算法设计和分析的原则 1

1.1 引言 1

1.2 分析算法的若干准则 2

算法一览表 5

1.3 搜索有序表——MEMBER（x,L） 8

1.4 在一个表中找最大元和次大元 12

1.5 在一个表中找最大元和最小元 13

1.6 分治法，递推方程和递推不等式 15

习题 18

注解和参考文献 21

第二章 整序 22

2.1 整序问题 22

2.2 一些比较整序算法 23

2.2.1 选择整序（selection sort） 23

2.2.2 插入整序（jnsertion sort） 24

2.2.3 冒泡整序（bubble sort） 24

2.2.4 歇尔整序（Shell sort） 25

2.2.5 快速整序（quick sort） 26

2.2.6 堆整序（heap sort） 29

2.3 比较整序的下界 32

2.4 归并整序（merge sorting） 34

2.5.1 带有足够大缓冲工作区（buffer）的线性时间算法 37

2.5 一个稳定的最优时空界限的整序算法——Z算法 37

2.5.2 非线性的原地归并算法 39

2.5.3 稳定的线性最优空间归并算法——Z算法 41

2.6 基数整序 44

2.6.1 桶整序 44

2.6.2 基数整序 45

2.6.3＊ 不等长字符串的字典整序 46

2.7 外部整序 49

2.7.1 归并整序 49

2.7.2 多路归并和替换选择 53

2.7.3 初始归并段的生成 55

2.7.4 多步归并整序 57

2.7.5 广义斐波拉奇数列 58

习题 59

注解和参考文献 60

3.1 二叉树搜索 61

第三章 搜索 61

3.2 2-3-4树 67

3.3 红-黑树 69

习题 72

注解和参考文献 73

第四章 集合运算 74

4.1 引言 74

4.2 散列 76

4.3 二叉树上实现集合操作 79

4.4 Union-Find程序 83

4.5 平衡树模式 90

4.6 字典与优先队列 91

4.7 可并堆 93

4.8 可毗连队列 94

习题 96

注解和参考文献 98

第五章 图的算法 99

5.1 基本概念 99

5.2 计算机中图的表示 100

5.3 图的遍历 101

5.4 强连通分支 106

5.5 双连通分支 108

5.6 两个中国人算法——回路判定 113

5.7 最小生成树 115

5.8 单源最短路径 119

5.9 所有点对之间的最短路径 121

510 传递闭包 122

习题 125

注解和参考文献 126

6.1 概述 127

第六章 串匹配 127

6.2 KMP算法 128

6.3 BM算法 132

6.4 RK算法 135

习题 137

注解和参考文献 138

第七章 几何问题算法 139

7.1 一些初等几何问题的算法 139

7.1.1 直线相交 139

7.1.2 倾角计算 140

7.1.3 是否包含在多边形内部 141

7.2 求凸包 142

7.2.1 卷包裹法 143

7.2.2 Graham扫描法 144

7.2.3 Floyed方法 146

7.3.1 水平与垂直线的相交问题 147

7.3 几何体相交问题 147

7.3.2 一般的直线相交问题 148

7.4 最近邻点问题 149

7.5 Voronoi图 152

习题 153

注解和参考文献 154

第八章 算法设计技术 155

8.1 分治法（Divide and Conquer） 155

8.2 贪心法（Greedy） 159

8.3 动态规划（Dynamic Programming） 162

8.4 回溯法（Backtracking） 169

8.5 分枝限界法（Branch and Bound） 174

习题 179

注解和参考文献 181

第九章 N？完全问题与近似算法 183

9.1 图灵机（Turing Machine） 183

9.2 不确定图灵机（Nondeterministic Turing Machine） 187

9.3 ？与N？类 191

9.4 COOK定理和N？完全问题 196

9.5 N？完全问题的近似算法 202

习题 209

注解和参考文献 210

第十章 概率算法和算法的概率分析 211

10.1 引言 211

10.2 概率算法的定义 212

10.3 求平面点集上最近点对的概率算法 212

10.4 判定素数的概率算法 217

10.4.1 概述 217

10.4.2 求二个整数的最大公约数的欧几里德辗转相除法 218

10.4.3 Fermat素数测试法 220

10.4.4 Miller和Rabin素数测试概率算法 221

10.5 ？ 222

10.6 Karp的有关算法概率分析的概念 222

习题 224

注解和参考文献 224

第十一章 VLSI中的并行算法 225

11.1 脉动方式的并行处理 225

11.2 分治方式的并行处理 233

11.3 计算模型和下界理论 241

习题 249

注解和参考文献 249

中文参考文献 250

Bibliograph 251