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

1.1　问题、算法和程序 1

第1章　基本概念 1

1.2　表述算法的方法 2

1.3　伪代码的语法规则 3

习题 6

第2章　数学预备知识 7

2.1　集合、函数关系 7

2.1.1　集合的表示 7

2.1.2　集合的子集 8

2.1.3　集合的运算 8

2.1.4　序列和多元组 8

2.2　函数关系 9

2.2.3　等价关系 10

2.3　布尔逻辑 10

2.2.2　二元关系的性质 10

2.2.1　二元关系 10

2.4　证明 11

2.4.1　直接证明法 11

2.4.2　间接证明 11

2.4.3　反证法 11

2.4.4　反例证明法 12

2.4.5　数学归纳法 12

2.5　取下整和取上整函数 13

2.6　取模运算 14

2.7　对数 14

2.8　级数求和 14

2.9　求和运算法则 15

2.10　用定积分解求和式的近似值 15

2.11　阶乘函数和二项式系数 16

2.11.1　阶乘 16

2.11.2　二项式系数 16

2.11.3　二项式定理 17

2.12　递推方程 19

2.12.1　常系数线性齐次递推式的求解 19

2.12.2　常系数线性非齐次递推方程的求解 21

2.12.3　扩展递推方程 22

2.12.4　用生成函数法求解递推关系 23

习题 26

第3章　算法复杂性分析 29

3.1　输入规模的度量 29

3.2　运行时间的度量单位 29

3.3　渐进符号基本增长率类型 33

3.3.1　上限 33

3.3.2　下限 33

3.3.3　Θ表示法 34

3.4　化简法则 34

3.5　非递归算法运行时间的计算 34

3.6　递归算法运行时间的计算 36

3.6.1　分治递归的定理方法 37

3.6.2　递归树的方法 38

3.7　算法的最佳、最差和平均复杂性 39

3.8　空间复杂性 41

习题 41

第4章　递归与迭代 45

4.1　递归 45

4.1.1　递归方法计算两个正整数相乘 45

4.1.2　递归方法计算阶乘函数 45

4.1.3　递归方法解全排列问题 46

4.2　迭代 48

4.2.1　迭代方法计算两个正整数相乘 48

4.2.2　迭代方法计算阶乘函数 48

4.2.3　迭代的方法解排列问题 48

4.3　梵天塔问题 49

4.3.1　递归方法解梵天塔问题 49

4.3.2　迭代方法解梵天塔问题 51

4.4.1　递归方法1解阿克曼函数 55

4.4　阿克曼函数 55

4.4.2　递归方法2解阿克曼函数 57

习题 57

第5章　递归与分形图形 59

5.1　递归与分形图形 59

5.2　涡旋曲线 59

5.3　康托（Cantor）三分集 60

5.4　谢尔宾斯基（Sierpinski）垫片 61

5.5　谢尔宾斯基（Sierpinski）地毯 62

5.6　科赫（Koch）曲线 64

习题 66

第6章　算法设计策略的比较与选择 68

6.1　求解斐波那契数列 68

6.1.1 时间复杂性为O(1.618)n+1递归算法 68

6.1.3　时间复杂性为O（n）、空间复杂性为O（l）迭代算法 69

6.1.2　时间和空间复杂性分别为O（n）迭代算法 69

6.1.4　时间复杂性为O（n）、空间复杂性为O（l）递归算法 70

6.1.5 时间复杂性为O（log n）、空间复杂性为O（l）递归算法1 70

6.1.6　时间复杂性为O（1og n）、空间复杂性为O（l）递归算法2 72

6.1.7　时间复杂性为O（1og n）、空间复杂性为O（l）递归算法3 73

6.2　最大子段和问题 74

6.2.1 时间复杂性为O（n3）算法1 74

6.2.2　时间复杂性为O（n3）算法2 75

6.2.3　时间复杂性为O（n2）算法 76

6.2.4　时间和空间复杂性分别为O（n2）算法1 76

6.2.5　时间和空间复杂性分别为O（n2）算法2 77

6.2.6　时间复杂性为O（n log n）算法 78

6.2.7　时间复杂性为O（n）算法 80

习题 80

第7章　排序 83

7.1　插入排序 83

7.2　起泡排序 84

7.3　选择排序 86

7.4　快速排序 88

7.5　归并排序 92

7.6　堆排序 95

7.7　计数排序 99

7.8　基数排序 102

7.9　排序问题的下限 104

习题 106

第8章　分治 109

8.1　求解数组中元素与x相等的个数 109

8.1.1　求解数组中元素与x相等的个数迭代算法 109

8.1.2　求解数组中元素与x相等的个数递归算法 109

8.1.3　求解数组中元素与x相等的个数分治递归算法 110

8.2　判断已排序数组中是否存在给定的元素x 110

8.2.2　判断已排序数组中是否存在给定的元素x分治递归算法 111

8.2.1　判断已排序数组中是否存在给定的元素x迭代算法 111

8.3　两个大整数相乘 112

8.3.1　两个大整数相乘迭代算法 112

8.3.2　两个大整数相乘分治递归算法1 113

8.3.3　两个大整数相乘分治递归算法2 115

8.3.4　两个大整数相乘分治递归算法3 116

8.3.5　两个大整数相乘分治递归算法4 116

8.4.1　两个矩阵相乘迭代算法 117

8.4　两个矩阵相乘 117

8.4.2　两个矩阵相乘分治递归算法1 118

8.4.3　两个矩阵相乘分治递归算法2 120

8.5　两个多项式乘积 121

8.5.1　两个多项式乘积迭代算法 122

8.5.2　两个多项式乘积分治递归算法1 123

8.5.3　两个多项式乘积分治递归算法2 124

习题 127

9.1.1　计算二项式系数递归算法 129

9.1　计算二项式系数 129

第9章　动态规划 129

9.1.2　计算二项式系数动态规划算法 130

9.2　正整数的分拆问题 132

9.2.1　正整数的分拆递归算法1 132

9.2.2　正整数的分拆递归算法2 134

9.2.3　正整数的分拆递归算法3 135

9.2.4　正整数拆分问题的上界 135

9.2.5　正整数拆分问题的下界 136

9.2.6　正整数的分拆动态规划算法 137

9.3　矩阵连乘问题 138

9.3.1　穷举法解矩阵连乘问题 139

9.3.2　递归方法解矩阵连乘问题 139

9.3.3　动态规划方法解矩阵连乘问题 142

9.4　最优二叉查找树 145

9.4.1　穷举法解最优二叉查找树 146

9.4.2　递归方法解最优二叉查找树 147

9.4.3　动态规划方法解最优二叉查找树 151

9.5　最长公共子序列问题 154

9.5.1　最长公共子序列递归算法 154

9.5.2　最长公共子序列动态规划算法 156

9.6　所有点对最短路径问题 157

9.6.1　所有点对最短路径递归算法 159

9.6.2　所有点对最短路径动态规划算法1 160

9.6.3　所有点对最短路径动态规划算法2 161

9.7　01背包问题 163

9.7.1　01背包递归算法 163

9.7.2　01背包动态规划算法 165

9.8　找零钱问题 168

9.8.1　找零钱递归算法 169

9.8.2　找零钱动态规划算法 170

习题 172

10.1　活动安排问题 175

第10章　贪心算法 175

10.2　分数背包问题 178

10.3　最短路径问题 180

10.4　最小生成树 182

10.4.1　prim算法 183

10.4.2　Kruskal算法 185

10.5　Huffman编码树 188

习题 192

第11章　回溯 194

11.1　八个皇后问题 194

11.2　旅行售货问题 198

11.3　01背包问题 201

11.4　子集合问题 202

11.4.1　子集合算法1 202

11.4.2　子集合算法2 203

11.4.3　子集合算法3 204

习题 205

12.1 15数字谜的问题 207

第12章　分支限界 207

12.2　分配任务问题 211

12.3　旅行售货问题 214

习题 216

13.1.1　寻找数组中最大元素迭代算法 217

13.1.2　寻找数组中最大元素递归算法 217

13.1　寻找数组中最大元素问题 217

第13章　寻找问题 217

13.1.3　寻找数组中最大元素分治递归算法 218

13.2　寻找数组中最小元素和最大元素问题 219

13.2.1　寻找数组中最小元素和最大元素迭代算法1 219

13.2.2　寻找数组中最小元素和最大元素迭代算法2 219

13.2.3　寻找数组中最小元素和最大元素分治递归算法 220

13.3　寻找数组中最大元素和次大元素问题 221

13.3.1　寻找数组中最大元素和次大元素锦标赛算法 221

13.4.1 寻找两个已排序数组的中位数算法1 223

13.4　寻找两个已排序数组的中位数问题 223

13.4.2　寻找两个已排序数组的中位数算法2 224

13.5　寻找两个已排序数组第k小元素问题 226

13.6　寻找数组中主元素问题 227

13.6.1　寻找数组中主元素算法1 227

13.6.2　寻找数组中主元素算法2 228

13.6.3　寻找数组中主元素算法3 228

13.7　选择数组中项和第k小元素问题 229

13.7.1　选择数组中项和第k小元素算法 229

13.7.2　划分元素5个为一组选择算法的时间复杂性 233

13.7.3　划分元素7个为一组选择算法的时间复杂性 235

13.7.4　划分元素3个为一组选择算法的时间复杂性 235

13.8　模式串匹配 235

13.8.1　直接匹配算法 236

13.8.2　模式匹配的一种改进算法 238

习题 241

14.1.1 x进制数相加算法 244

第14章　算术运算、数值算法 244

14.1　加法 244

14.1.2　二进制数相加算法 245

14.2　减法 246

14.2.1 x进制数相减算法 246

14.2.2　二进制数相减算法 247

14.3　乘法 249

14.3.1 x进制数相乘算法 249

14.3.2　二进制数相乘算法 250

14.4　除法 251

14.4.1 x进制数相除算法 251

14.4.2　二进制数相除算法 252

14.5　整数幂 253

14.5.1　整数幂迭代算法 253

14.5.2　整数幂递归算法 253

14.6　二进制幂 254

14.5.3　整数幂分治迭代算法 254

14.5.4　整数幂分治递归算法 254

14.7　模取幂运算 255

14.8　模取二进制幂运算 256

14.9　多项式的快速求值 257

14.9.1　多项式求值算法1 257

14.9.2　多项式求值算法2 258

14.9.3　伯恩斯坦（Bernstein）多项式求值 259

习题 259

第15章　数论算法 262

15.1　最大公约数问题 262

15.1.1　最大公约数迭代算法1 262

15.1.2　最大公约数迭代算法2 262

15.1.3　最大公约数迭代算法3 263

15.1.4　最大公约数递归算法 263

15.3.1　扩展欧几里得递归算法 264

15.3　扩展欧几里得算法 264

15.2　求最小公倍数 264

15.3.2　扩展欧几里得迭代算法 265

15.4　素性检测 267

15.4.1　素性检测算法1 267

15.4.2　素性检测算法2 267

15.4.3　爱拉托斯散（Eratosthenes）筛选算法 268

15.4.4　素性检测算法3 269

15.4.5　素性检测算法4 269

15.4.6　素性检测算法5 270

15.4.7　素性检测算法6 270

15.5 RSA算法 272

15.5.1　欧拉定理 272

15.5.2　RSA加密与解密算法 273

习题 274

主要参考文献 276