计算机算法分析与设计PDF|Epub|txt|kindle电子书版本网盘下载

计算机算法分析与设计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）递归算法170

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

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

6.2　最大子段和问题74

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

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

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

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

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

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　判断已排序数组中是否存在给定的元素x110

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

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

8.3　两个大整数相乘112

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

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

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

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

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

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

8.4　两个矩阵相乘117

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

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

8.5　两个多项式乘积121

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

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

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

习题127

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

9.1　计算二项式系数129

第9章　动态规划129

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

9.2　正整数的分拆问题132

9.2.1　正整数的分拆递归算法1132

9.2.2　正整数的分拆递归算法2134

9.2.3　正整数的分拆递归算法3135

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　所有点对最短路径动态规划算法1160

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

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　子集合算法1202

11.4.2　子集合算法2203

11.4.3　子集合算法3204

习题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　寻找数组中最小元素和最大元素迭代算法1219

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

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

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

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

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

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

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

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

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

13.6.1　寻找数组中主元素算法1227

13.6.2　寻找数组中主元素算法2228

13.6.3　寻找数组中主元素算法3228

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　多项式求值算法1257

14.9.2　多项式求值算法2258

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

习题259

第15章　数论算法262

15.1　最大公约数问题262

15.1.1　最大公约数迭代算法1262

15.1.2　最大公约数迭代算法2262

15.1.3　最大公约数迭代算法3263

15.1.4　最大公约数递归算法263

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

15.3　扩展欧几里得算法264

15.2　求最小公倍数264

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

15.4　素性检测267

15.4.1　素性检测算法1267

15.4.2　素性检测算法2267

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

15.4.4　素性检测算法3269

15.4.5　素性检测算法4269

15.4.6　素性检测算法5270

15.4.7　素性检测算法6270

15.5 RSA算法272

15.5.1　欧拉定理272

15.5.2　RSA加密与解密算法273

习题274

主要参考文献276