算法设计与分析【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

算法设计与分析PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1.1 算法简介1

1.1.1 算法的定义1

第1章 算法概述1

1.1.2 算法的重要性2

1.1.3 一个简单例子的算法表示2

1.1.4 求最大公约数算法的细化4

1.2 常见问题的类型6

1.2.1 排序问题6

1.2.2 搜索问题7

1.2.3 字符串问题7

1.2.4 图论问题8

1.2.5 组合数学问题8

1.2.6 几何问题8

1.2.7 数值计算问题8

1.2.8 加密问题8

1.3.1 了解问题的内容9

1.3.2 确定计算设备的能力9

1.3 解决问题的一般步骤9

1.3.3 选择精确或者近似的算法10

1.3.4 选择合适的数据结构10

1.3.5 选择算法设计技术10

1.3.6 设计算法11

1.3.7 确认算法的正确性11

1.3.8 对该算法的分析12

1.3.9 对算法的程序实现12

一、选择题13

小结13

综合练习一13

二、问答题14

第2章 算法设计基础15

2.1 常用数据结构15

2.1.1 数组与链表15

2.1.2 栈与队列17

2.1.3 图与树18

2.1.4 集合与字典26

2.2.1 分治法27

2.2 常用算法设计方法27

2.2.2 贪婪法29

2.2.3 动态规划法30

2.2.4 回溯法31

2.2.5 分支限定法31

小结31

综合练习二32

一、选择题32

二、问答题33

第3章 算法分析基础34

3.1 算法分析的基本框架34

3.1.1 确定算法输入量34

3.1.2 确定算法时间34

3.1.3 算法时间复杂度的渐进表示法36

3.1.4 具体输入对算法执行效率的影响37

3.1.5 算法分析框架的摘要重述38

3.2 时间复杂度渐进分析的数学基础38

3.2.1 渐进性态的数学概念38

3.2.2 算法渐进分析的数学表达40

3.2.3 渐进分析的重要方法与结论41

3.2.4 算法渐进复杂度分析的重要性42

3.3 算法分析举例43

3.3.1 非递归算法分析43

3.3.2 递归算法分析46

3.4 递归算法分析再讨论51

3.4.1 序列与递推关系51

3.4.2 递推关系的计算方法51

小结53

综合练习三54

一、选择题54

二、问答题55

第4章 排序算法56

4.1 排序相关的概念56

4.1.1 偏序集56

4.1.2 排序算法复杂性的计算56

4.2 交换排序57

4.2.1 冒泡排序57

4.2.2 双向冒泡排序59

4.2.3 快速排序60

4.3 插入排序64

4.3.1 直接插入排序64

4.3.2 折半插入排序66

4.3.3 希尔排序67

4.3.4 链表插入排序68

4.4 选择排序70

4.4.1 直接选择排序70

4.4.2 锦标赛排序71

4.5 堆与堆排序73

4.5.1 堆的概念73

4.5.2 堆的构建与堆结点的插入74

4.5.3 堆结点的删除76

4.5.4 堆排序76

4.6 归并排序77

4.6.1 合并过程78

4.6.2 递归的归并排序78

4.7 统计排序79

4.6.3 迭代的归并排序79

4.7.1 比较统计排序80

4.7.2 分布统计排序81

4.8 外排序简介82

小结83

综合练习四84

一、选择题84

二、问答题85

5.1.2 搜索环境86

5.1.3 索引的使用86

5.1 搜索相关的概念86

5.1.1 搜索表与关键字86

第5章 搜索算法86

5.1.4 搜索算法效率的衡量87

5.2 静态搜索表的算法87

5.2.1 顺序搜索算法87

5.2.2 有序表的折半搜索88

5.2.3 Fibonacci搜索92

5.3 二叉搜索树搜索95

5.3.1 二叉搜索树相关概念96

5.3.2 二叉搜索树的搜索96

5.3.3 二叉搜索树的插入98

5.3.4 二叉搜索树的删除99

5.3.5 二叉搜索树效率分析100

5.4 AVL树101

5.4.1 AVL树相关概念101

5.4.2 AVL树的平衡旋转102

5.4.3 AVL树的插入104

5.4.4 AVL树的删除105

5.4.5 AVL树的高度106

5.5 2-3树107

5.5.1 基本概念107

5.5.2 搜索算法107

5.5.3 插入算法107

5.5.4 2-3树的高度108

5.6 最优二叉搜索树108

5.6.1 一般情况下时间复杂度计算108

5.6.2 最优二叉搜索树构造算法110

5.6.3 最优二叉搜索树构造实例112

5.7 索引结构113

5.7.1 线性索引结构114

5.7.2 多级索引115

5.7.3 动态m路搜索树116

5.7.4 平衡m路搜索树（B树）117

5.8 散列方法118

5.8.1 散列方法介绍118

5.8.3 散列函数的建立119

5.8.2 散列方法的过程119

5.8.4 冲突的解决121

5.8.5 散列效率的衡量122

小结122

综合练习五123

一、选择题123

二、问答题124

6.1.2 数据表的模式125

6.1.1 数据表元素的惟一性125

6.1 搜索问题扩展125

第6章 类搜索算法与字符串匹配算法125

6.1.3 确定数据表中不同的元素127

6.1.4 确定数据表第k小的元素128

6.2 搜索与排序130

6.2.1 比较排序算法复杂度130

6.2.2 搜索算法与排序131

6.2.3 预排序算法132

6.3 字符串匹配算法133

6.3.1 字符串匹配的基本概念133

6.3.2 直接匹配算法133

6.3.3 KMP算法135

6.3.4 Horspool算法139

6.3.5 BM算法142

6.3.6 RK算法145

综合练习六147

一、选择题147

小结147

二、问答题148

第7章 图与树相关算法149

7.1 二叉树的遍历149

7.1.1 中序遍历149

7.1.2 前序遍历150

7.1.3 后序遍历151

7.1.4 二叉树遍历的应用152

7.2.1 二叉树的确定154

7.2 二叉树的计数154

7.2.2 中序遍历的非递归算法155

7.2.3 二叉树个数155

7.3 图的遍历156

7.3.1 深度优先搜索157

7.3.2 广度优先搜索160

7.3.3 DFS与BFS比较162

7.3.4 DFS的应用：重连通图163

7.4.2 带权图的路径长度164

7.4.1 图的路径长度164

7.4 图的路径与带权路径164

7.3.5 BFS的应用：最短路径164

7.4.3 带权路径的表示方法165

7.4.4 路径长度问题分类165

7.5 两点之间的最短路径166

7.5.1 非负权图的Dijkstra算法166

7.5.2 任意权值的Bellman-Ford算法168

7.6.1 Warshall算法171

7.6 任意点之间的最短路径171

7.6.2 Floyd算法172

7.7 最小生成树174

7.7.1 Kruskal算法174

7.7.2 Prim算法176

7.8 最大流量问题177

7.8.1 网络流量问题与线性规划177

7.8.2 最大流量的Edmonds-Karp算法178

7.9 最小费用最大流量问题183

7.10.1 最小带权路径长度186

7.10 霍夫曼树186

7.10.2 霍夫曼树的应用187

7.11 图的应用举例188

7.11.1 七桥问题188

7.11.2 人狼羊菜渡船问题189

7.11.3 课程安排问题190

小结191

综合练习七191

一、选择题191

二、问答题193

第8章 几何问题算法194

8.1 几何形体在计算机中的表示194

8.1.1 基本几何形体的表示194

8.1.2 直线段的显示算法194

8.2 初等几何问题算法197

8.2.1 直线相交判断197

8.2.2 直线的倾角199

8.3 最近邻点问题算法199

8.3.1 最近邻点的一般解法199

8.3.2 最近邻点问题的分治法200

8.4 凸包问题算法203

8.4.1 包问题的一般算法203

8.4.2 包问题的分治法204

小结205

综合练习八205

一、选择题205

二、问答题206

第9章 数值算法207

9.1 杨辉三角207

9.2 多项式求值208

9.2.1 一般算法208

9.2.2 Horner法则209

9.2.3 二进制求幂算法210

9.3 大整数乘法211

9.3.1 算法思想212

9.4.1 线性方程组213

9.4 线性方程组与高斯消元法213

9.3.3 算法分析213

9.3.2 算法伪代码213

9.4.2 高斯消元法214

9.4.3 矩阵的LU分解216

9.5 矩阵基本运算217

9.5.1 矩阵乘法217

9.5.2 矩阵的逆218

小结219

9.5.3 矩阵行列式219

综合练习九220

一、选择题220

二、问答题220

第10章 组合问题算法221

10.1 排列问题221

10.1.1 降低规模求解算法221

10.1.2 Johnson-Trotter算法222

10.1.3 字典排序算法222

10.2.1 降低规模的幂集算法223

10.2.2 求幂集的位串法223

10.2 幂集问题223

10.3 背包问题224

10.3.1 超递增序列背包问题的求解224

10.3.2 背包问题的穷举法224

10.3.3 动态规划法求解背包问题225

10.4 旅行家问题227

小结227

一、选择题228

综合练习十228

二、问答题229

第11章 加密算法与安全机制230

11.1 加密算法230

11.1.1 DES算法230

11.1.2 RSA算法236

11.1.3 MD5算法241

11.1.4 算法实现与性能比较244

11.2 安全机制244

11.2.1 鉴别协议244

11.2.2 消息完整性协议247

11.2.3 公开密钥分发协议248

小结251

综合练习十一252

一、选择题252

二、问答题253

第12章 算法复杂性理论简介254

12.1 算法问题254

12.1.1 可解问题与不可解问题254

12.1.2 P问题与NP问题255

12.1.3 NP理论的核心问题256

12.2 图灵机简介256

小结258

综合练习十二258

一、选择题258

二、问答题259

附录 算法伪代码索引260

参考答案263

参考文献268