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

第1章 与算法相关的数学问题 1

1.1 复杂性分析初步 2

1.1.1 空间复杂度 3

1.1.2 时间复杂度 4

1.2 复杂性的计量 5

1.3 数学归纳法 8

1.3.1 第一数学归纳法 8

1.3.2 第二数学归纳法 9

1.3.3 结构归纳法 9

1.4 生成函数 10

1.4.1 基本性质 11

1.4.2 生成函数的计算 12

1.5 递归方程求解 13

1.5.1 递推法 14

1.5.2 公式解法 16

1.5.3 母函数法 18

1.6 NP问题 19

思考题 20

第2章 递归的应用 23

2.1 第1类递归 24

2.2 二叉树的递归遍历 37

2.3 图的遍历 44

2.3.1 图的深度优先搜寻法 44

2.3.2 图的广度优先算法 47

2.4 递归与非递归的转换 51

思考题 55

第3章 迭代算法 58

3.1 常见的迭代 58

3.2 求方程的根 59

3.2.1 牛顿迭代法 59

3.2.2 二分法 60

3.2.3 实例 60

3.3 雅可比迭代法与高斯-塞德尔迭代法 66

3.3.1 雅可比迭代法 66

3.3.2 高斯-塞德尔迭代法 69

3.3.3 迭代收敛的充分条件 70

思考题 76

第4章 常见排序算法 78

4.1 常见的内排序 78

4.1.1 插入排序法 78

4.1.2 交换排序 82

4.1.3 选择排序 85

4.1.4 基数排序 89

4.1.5 归并排序 92

4.1.6 计数排序 95

4.2 算法性能分析 96

思考题 106

第5章 动态规划法 108

5.1 最短路径问题 114

5.1.1 Dijkstra算法 114

5.1.2 Bellman-Ford算法 117

5.1.3 Floyd算法 121

5.2 最长公共子序列 126

5.3 01背包问题 133

5.4 计算矩阵连乘积 137

5.5 Bitonic旅行路线问题 144

思考题 148

第6章 回溯法 151

6.1 4皇后问题 153

6.2 排列组合问题 157

6.3 01背包问题 159

6.4 任务分配问题 164

6.5 数码串珠 167

6.6 桥本分数式 169

思考题 172

第7章 贪心算法 176

7.1 01背包 179

7.2 哈夫曼编码 182

7.3 拓扑排序 188

7.4 最小生成树 194

7.4.1 Kruskal算法 194

7.4.2 Prim算法 198

7.5 汽车加油问题 201

思考题 204

第8章 分治算法 207

8.1 二分查找 209

8.2 大整数的乘法 211

8.3 棋盘覆盖问题 215

8.4 循环赛日程表 218

8.5 全排列 224

8.6 矩阵乘法 226

思考题 233

第9章 概率算法 235

9.1 数值概率算法 235

9.1.1 随机数 235

9.1.2 用随机投点法计算pi值 238

9.1.3 计算定积分 239

9.2 舍伍德算法 240

9.3 拉斯维加斯算法 242

9.4 蒙特卡罗算法 248

思考题 252

第10章 近似算法 253

10.1 旅行售货员问题 255

10.2 装箱问题 256

10.3 集合覆盖问题 259

10.4 子集和问题 260

思考题 263

第11章 分支限界法 264

11.1 01背包 266

11.2 最短路径 272

11.3 装载问题 277

11.4 旅行售货员问题 282

11.5 布线问题 290

思考题 299

第12章 遗传算法 302

12.1 遗传算法的基本原理 302

12.1.1 全局优化问题 302

12.1.2 遗传编码 303

12.1.3 群体设定 304

12.1.4 适应度函数 305

12.1.5 遗传算子 306

12.1.6 循环终止条件 311

12.1.7 控制参数 311

12.2 01背包问题 312

12.3 旅行家问题 320

思考题 329

第13章 蚁群算法 330

13.1 蚁群算法简介 330

13.2 TSP问题 332

思考题 343

第14章 查找 344

14.1 查找的基本概念 344

14.1.1 查找表和查找 344

14.1.2 查找表的数据结构表示 344

14.1.3 平均查找长度ASL 344

14.2 顺序查找 345

14.2.1 顺序查找方法适用于线性表的顺序存储结构 345

14.2.2 顺序查找的平均查找长度 345

14.2.3 该算法的优缺点 345

14.3 二分查找 345

14.3.1 基本思想 346

14.3.2 查找算法 346

14.3.3 平均查找长度 347

14.3.4 二分查找的优点和缺点 347

14.4 分块查找 348

14.4.1 存储结构 348

14.4.2 基本思想 348

14.4.3 算法分析 348

14.4.4 分块查找的优缺点 349

14.5 二叉排序树的查找 349

14.6 哈希查找 354

思考题 358

主要参考文献 361