算法分析与设计及案例教程PDF电子书下载

第1章 绪论 1

1.1 什么是算法 1

1.1.1 算法的由来 1

1.1.2 算法的发展 3

1.1.3 算法的例子 4

1.2 重要的问题类型 5

1.2.1 排序 6

1.2.2 查找 6

1.2.3 字符串匹配 6

1.2.4 图问题 7

1.2.5 组合问题 7

1.2.6 几何问题 7

1.2.7 数值问题 8

1.3 基本数据结构 8

1.3.1 线性结构 8

1.3.2 树结构 8

1.3.3 图结构 9

1.3.4 集合 9

1.3.5 数据的物理结构 10

1.4 算法问题求解基础 10

1.4.1 算法求解框架 10

1.4.2 算法设计步骤 10

1.5 算法的表示 14

1.6 为什么学习算法 15

总结 16

习题1 16

第2章 算法效率分析基础 17

2.1 算法分析框架 17

2.1.1 算法分析概述 17

2.1.2 算法正确性分析 17

2.1.3 时空效率分析 17

2.1.4 算法分析过程 19

2.2 渐进符号和基本效率类型 20

2.2.1 三种渐进符号 20

2.2.2 渐进符号的特性 20

2.2.3 基本效率类型 21

2.3 非递归算法的数学分析方法 22

2.4 递归算法的数学分析 26

2.4.1 递归算法的数学分析方法 26

2.4.2 斐波那契数列 29

2.5 算法的其他分析方法 31

总结 32

习题2 32

第3章 蛮力法 33

3.1 概述 33

3.2 排序问题 35

3.2.1 选择排序 35

3.2.2 冒泡排序 36

3.3 查找问题 37

3.3.1 顺序查找 38

3.3.2 字符串匹配 38

3.4 几何问题 39

3.4.1 最近对问题 40

3.4.2 凸包问题 40

3.5 组合问题 42

3.5.1 旅行商问题 42

3.5.2 背包问题 44

总结 45

习题3 45

第4章 分治法 46

4.1 概述 46

4.2 分治法的基本策略及步骤 46

4.2.1 分治法的基本策略 46

4.2.2 分治法的基本步骤 47

4.3 排序问题 48

4.3.1 合并排序 48

4.3.2 快速排序 49

4.4 查找问题 51

4.4.1 折半查找 51

4.4.2 二叉树遍历及其相关特性 53

4.5 数值计算问题 54

4.5.1 大整数乘法 54

4.5.2 Strassen矩阵乘法 56

4.6 几何问题 58

4.6.1 用分治法解最近对问题 58

4.6.2 用分治法解凸包问题 59

4.7 分析分治法在安排循环赛中的应用 60

总结 62

习题4 62

第5章 分治策略变体——减治策略和变治策略 64

5.1 减治策略 64

5.1.1 插入排序 65

5.1.2 拓扑排序 67

5.1.3 生成组合对象的算法 68

5.1.4 减常因子算法 71

5.1.5 减可变规模算法 73

5.2 变治策略 75

5.2.1 排序问题 75

5.2.2 平衡查找树 80

5.2.3 霍纳法则和二进制幂 86

5.2.4 问题化简 88

总结 89

习题5 89

第6章 动态规划 91

6.1 概述 91

6.2 算法特点 93

6.2.1 备忘录方法 94

6.2.2 最优化原理 98

6.2.3 求解步骤 98

6.3 矩阵连乘问题 99

6.4 最长公共子序列 104

6.5 0-1背包问题 107

6.6 最大子段和 113

6.7 最优二叉查找树 116

总结 122

习题6 122

第7章 时空权衡技术 125

7.1 时空权衡策略 125

7.2 计数排序 126

7.3 字符串匹配 128

7.4 散列法 134

总结 139

习题7 139

第8章 贪心算法 141

8.1 概述 141

8.1.1 贪心算法的基本要素 142

8.1.2 贪心算法的求解过程 142

8.2 活动安排问题 143

8.3 背包问题 146

8.4 最小生成树问题 148

8.4.1 Prim算法 150

8.4.2 Kruskal算法 153

8.5 单源（点）最短路径问题 158

8.6 哈夫曼编码 162

总结 168

习题8 168

第9章 回溯法和分支限界法 171

9.1 回溯法 171

9.1.1 概述 171

9.1.2 子集和问题 176

9.1.3 n皇后问题 178

9.1.4 哈密顿回路 180

9.1.5 装载问题 182

9.2 分支限界法 186

9.2.1 概述 186

9.2.2 0-1背包问题 191

9.2.3 任务分配问题 194

9.2.4 多段图的最短路径问题 199

9.2.5 旅行商问题 204

总结 210

习题9 210

第10章 NP完全性理论 212

10.1 判定问题和最优化问题 212

10.2 P类问题 214

10.3 NP类问题 215

10.4 NP完全问题 216

10.5 典型的NP完全问题 218

10.6 其他NP完全问题 220

10.7 NP完全问题的计算机处理 221

总结 222

习题10 222

第11章 案例精选 223

11.1 果园篱笆问题 223

11.2 空中飞行管理问题 223

11.3 去数问题 224

11.4 极差问题 224

11.5 最优合并问题 225

11.6 在棋盘中实现从初始布局到目标布局的转变 226

11.7 商店购物问题 227

11.8 旅游预算问题 229

11.9 防卫导弹问题 231

11.10 钓鱼问题 232

11.11 胖男孩问题 234

11.12 护卫队问题 235

参考文献 237