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

第1章 算法引论 1

1.1算法的基本概念 2

1.1.1算法的重要特性 2

1.1.2算法的基本内容 3

1.2算法分析 4

1.2.1计算时间的渐进表示 6

1.2.2常用的整数求和公式 8

1.2.3作时空性能分布图 9

1.3最优算法概述 10

本章小结 10

习题与思考 10

第2章 递归算法与分治算法 11

2.1递归算法的实现机制 12

2.1.1递归函数调用的一般形式 12

2.1.2值的回传 13

2.1.3递归函数调用的内部操作 14

2.2递归算法的设计 14

2.3递归算法转化为非递归算法 20

2.4递归关系式的计算 24

2.4.1生成函数及其性质 24

2.4.2利用生成函数求解递归关系式 26

2.4.3 k阶常系数线性齐次递归关系式 29

2.4.4 k阶常系数线性非齐次递归关系式 31

2.5分治算法的基本设计原理 33

2.6分治算法求解二分搜索问题 37

2.7分治算法求解归并排序问题 41

2.8分治算法求解快速排序问题 45

2.8.1数组的划分 46

2.8.2快速排序算法的实现 47

2.8.3快速排序算法的最坏情况分析 48

2.8.4快速排序算法的平均情况分析 49

2.9分治算法求解选择问题 50

2.9.1选择问题的思想方法 51

2.9.2选择问题的算法实现 52

2.9.3关于选择问题的算法分析 54

本章小结 55

课后阅读材料 55

习题与思考 59

第3章 贪心算法 60

3.1贪心算法的设计思想 62

3.2贪心算法求解背包问题 63

3.2.1背包问题贪心算法的设计思想 64

3.2.2背包问题贪心算法的分析 66

3.3贪心算法求解单源点最短路径问题 67

3.3.1单源点最短路径贪心算法的设计思想 67

3.3.2单源点最短路径贪心算法的实现 68

3.3.3单源点最短路径贪心算法的分析 71

3.4贪心算法求解最小成本生成树问题 71

3.4.1最小成本生成树问题 71

3.4.2普里姆算法的实现过程 72

3.4.3普里姆算法的分析 75

3.4.4克鲁斯卡尔算法的思想方法 76

3.4.5集合的树表示和不相交集合的合并——树结构应用实例 76

3.4.6克鲁斯卡尔算法的实现过程 79

3.4.7克鲁斯卡尔算法的分析 81

本章小结 82

课后阅读材料 82

习题与思考 88

第4章 动态规划算法 90

4.1动态规划算法的设计思想 91

4.2多段图的最小成本问题 93

4.2.1多段图的决策过程 94

4.2.2多段图模型动态规划算法的具体实现 96

4.2.3多段图模型的求解实例 97

4.3资源分配问题 99

4.3.1资源分配方案的决策过程 100

4.3.2动态规划算法求解资源分配问题的实现 103

4.4 0/1背包问题 105

4.4.1 0/1背包问题的求解过程 105

4.4.2 0/1背包问题的动态规划算法 107

4.5最长公共子序列问题 108

4.5.1最长公共子序列的搜索过程 109

4.5.2最长公共子序列的动态规划算法实现 111

本章小结 113

课后阅读材料 113

习题与思考 120

第5章 回溯算法 123

5.1回溯算法的设计思想 124

5.2回溯算法的设计框架 128

5.3 0/1背包问题 131

5.3.1回溯算法求解0/1背包问题的求解过程 131

5.3.2回溯算法求解0/1背包问题的算法实现 134

5.4装箱问题 137

5.4.1装箱问题实现 137

5.4.2递归回溯算法设计 138

5.4.3上界函数 139

5.4.4迭代回溯算法设计 142

5.5最大通信团体问题 144

5.5.1最大团体问题的描述及求解思路 144

5.5.2最大通信团体问题的描述及求解思路 144

本章小结 148

课后阅读材料 148

习题与思考 151

第6章 随机化算法 154

6.1随机化算法引言 155

6.1.1随机化算法的分类 156

6.1.2随机数产生器 156

6.2谢伍德算法 157

6.2.1随机化快速排序算法 158

6.2.2随机化选择算法 159

6.3拉斯维加斯算法 162

6.4蒙特卡罗算法 165

本章小结 168

习题与思考 169

第7章 图论与网络流问题 170

7.1图的遍历 171

7.1.1图的深度优先搜索遍历算法 171

7.1.2图的广度优先搜索遍历算法 175

7.1.3无向图的割点 177

7.1.4有向图的强连通分支 180

7.2网络的最大流量问题 183

7.2.1必备的数学知识 183

7.2.2最大流量算法与最大容量扩展算法 185

7.2.3最短路径扩展算法 189

7.3二部图的最大匹配问题 194

7.3.1必备的数学知识 194

7.3.2二部图的最大匹配的匈牙利树算法 195

本章小结 203

课后阅读材料 203

习题与思考 209

第8章 智能算法掠影 215

8.1遗传算法 215

8.1.1遗传算法的基本机理 216

8.1.2遗传算法的求解步骤 218

8.2粒子群优化算法 219

8.2.1群智能算法和粒子群优化算法概述 219

8.2.2粒子群优化算法研究及应用 220

8.3蚁群算法 222

8.3.1蚁群算法理论 222

8.3.2蚁群算法的研究及应用 224

8.4免疫算法 225

8.4.1免疫算法的提出 225

8.4.2免疫算法的理论 226

8.4.3免疫算法的应用及其发展趋势 229

本章小结 230

参考文献 232