算法设计与分析——C++语言描述（第4版）
定价：￥69.00
作者： 陈慧南
出版时间：2025-01
出版社：电子工业出版社
普通高等教育“十一五”国家级规划教材
- 电子工业出版社
- 9787121483325
- 4版
- 540843
- 60266912-9
- 平塑
- 16开
- 2025-01
- 524
- 312
- 工学
- 计算机类
- 计算机科学与技术
- 本科 研究生及以上
内容简介
本书为普通高等教育“十一五”国家级规划教材。 本书内容分为3部分：算法和算法分析、算法设计策略及求解困难问题。第1部分介绍算法问题求解基础和算法分析基础，以及两种新的数据结构：伸展树与跳表；第2部分讨论常用的算法设计策略，包括基本搜索和遍历方法、分治法、贪心法、动态规划法、回溯法和分枝限界法；第3部分介绍NP完全问题、随机算法、近似算法、遗传算法和密码算法，并对现代密码学和数论做了简要论述。本书结构清晰、内容翔实、逻辑严谨、讲解深入浅出。书中算法有完整的C++程序，这些程序构思精巧，有详细注释，并且已在C++环境下编译通过能正确运行。它们既是讲解算法设计的示例，帮助理解和掌握复杂抽象的算法设计，也是很好的C++程序设计示例。书中包含大量实例，并附有丰富的习题，便于教学和自学。本书可作为高等学校计算机及其他相关专业本科生和研究生“算法设计与分析”课程的教材或参考书，是“算法与数据结构”或“数据结构”课程有益的教学参考书，也可供计算机相关从业者及其他希望了解和学习算法知识的人员参考。
目录
第1部分 算法和算法分析
第1章 算法问题求解基础 1
1.1 算法概述 1
1.1.1 什么是算法 1
1.1.2 为什么学习算法 3
1.2 问题求解方法 3
1.2.1 问题和问题求解 4
1.2.2 问题求解过程 4
1.2.3 软件生命周期 5
1.3 算法设计与分析 5
1.3.1 算法问题求解过程 5
1.3.2 如何设计算法 6
1.3.3 如何表示算法 6
1.3.4 如何确认算法 6
1.3.5 如何分析算法 7
1.4 递归和归纳 7
1.4.1 递归 7
1.4.2 递归算法示例 9
1.4.3 归纳证明 11
习题1 13
第2章 算法分析基础 14
2.1 算法复杂度 14
2.1.1 什么是好的算法 14
2.1.2 影响程序执行时间的因素 15
2.1.3 算法的时间复杂度 16
2.1.4 使用程序步分析算法 17
2.1.5 算法的空间复杂度 18
2.2 渐近表示法 19
2.2.1 大O记号 19
2.2.2 Ω记号 20
2.2.3 Θ记号 21
2.2.4 小o记号 21
2.2.5 算法按时间复杂度分类 21
2.3 递推关系 22
2.3.1 递推方程 22
2.3.2 替换方法 23
2.3.3 迭代方法 23
2.3.4 递归树 23
2.3.5 主方法 25
2.4 分摊分析 25
2.4.1 聚集分析 26
2.4.2 会计方法 26
2.4.3 势能方法 27
习题2 28
第3章 伸展树与跳表 31
3.1 伸展树 31
3.1.1 二叉搜索树 31
3.1.2 自调节树和伸展树 31
3.1.3 伸展操作 32
3.1.4 伸展树类 34
3.1.5 旋转的实现 34
3.1.6 插入运算的实现 35
3.1.7 分摊分析 37
3.2 跳表 39
3.2.1 什么是跳表 39
3.2.2 跳表类 40
3.2.3 层次分配 42
3.2.4 插入运算的实现 43
3.2.5 性能分析 44
习题3 45
第2部分 算法设计策略
第4章 基本搜索和遍历方法 46
4.1 基本概念 46
4.2 图的搜索和遍历 47
4.2.1 搜索方法 47
4.2.2 邻接表类 48
4.2.3 广度优先搜索 49
4.2.4 深度优先搜索 51
4.3 双连通分量 53
4.3.1 基本概念 53
4.3.2 发现关节点 54
4.3.3 构造双连通图 58
4.4 与或图 58
4.4.1 问题分解 58
4.4.2 判断与或树是否可解 60
4.4.3 构建解树 61
4.5 区间最值查询（RMQ） 62
4.5.1 区间信息维护与查询 62
4.5.2 ST算法求解RMQ问题 63
4.6 最近公共祖先（LCA） 65
4.6.1 概述 65
4.6.2 倍增法求解LCA问题 66
4.6.3 在线RMQ法求解LCA问题 68
4.6.4 Tarjan算法求解LCA问题 70
习题4 73
第5章 分治法 75
5.1 一般方法 75
5.1.1 分治法的基本思想 75
5.1.2 算法分析 76
5.1.3 数据结构 77
5.2 求最大、最小元 78
5.2.1 分治法求解 78
5.2.2 时间分析 79
5.3 二分搜索 80
5.3.1 分治法求解 80
5.3.2 对半搜索 81
5.3.3 二叉判定树 82
5.3.4 搜索算法的时间下界 84
5.4 排序问题 85
5.4.1 合并排序 85
5.4.2 快速排序 87
5.4.3 排序算法的时间下界 91
5.5 选择问题 92
5.5.1 分治法求解 92
5.5.2 随机选择主元 93
5.5.3 线性时间选择算法 94
5.5.4 时间分析 96
5.5.5 允许重复元素的选择算法 97
5.6 斯特拉森矩阵乘法 97
5.6.1 分治法求解 97
5.6.2 斯特拉森矩阵乘法简介 98
习题5 99
第6章 贪心法 102
6.1 一般方法 102
6.2 背包问题 103
6.2.1 问题描述 103
6.2.2 贪心法求解 104
6.2.3 算法正确性 105
6.3 带时限的作业排序问题 106
6.3.1 问题描述 106
6.3.2 贪心法求解 107
6.3.3 算法正确性 108
6.3.4 可行性判定 108
6.3.5 作业排序贪心算法 109
6.3.6 改进算法 110
6.4 最佳合并模式 112
6.4.1 问题描述 113
6.4.2 贪心法求解 113
6.4.3 算法正确性 115
6.5 最小代价生成树 116
6.5.1 问题描述 116
6.5.2 贪心法求解 116
6.5.3 普里姆算法 117
6.5.4 克鲁斯卡尔算法 119
6.5.5 算法正确性 121
6.6 单源最短路径 122
6.6.1 问题描述 122
6.6.2 贪心法求解 122
6.6.3 迪杰斯特拉算法 123
6.6.4 算法正确性 125
6.7 磁带最优存储 127
6.7.1 单带最优存储 127
6.7.2 多带最优存储 128
6.8 贪心法的基本要素 129
6.8.1 最优量度标准 129
6.8.2 最优子结构 129
习题6 130
第7章 动态规划法 133
7.1 一般方法和基本要素 133
7.1.1 一般方法 133
7.1.2 基本要素 134
7.1.3 多段图问题 134
7.1.4 资源分配问题 137
7.1.5 关键路径问题 138
7.2 每对结点间的最短路径 140
7.2.1 问题描述 140
7.2.2 动态规划法求解 140
7.2.3 弗洛伊德算法 141
7.2.4 算法正确性 143
7.3 矩阵连乘 143
7.3.1 问题描述 143
7.3.2 动态规划法求解 144
7.3.3 矩阵连乘算法 145
7.3.4 备忘录方法 147
7.4 最长公共子序列 147
7.4.1 问题描述 147
7.4.2 动态规划法求解 148
7.4.3 最长公共子序列算法 149
7.4.4 改进算法 151
7.5 最优二叉搜索树 151
7.5.1 问题描述 151
7.5.2 动态规划法求解 151
7.5.3 最优二叉搜索树算法 153
7.6 0/1背包问题 155
7.6.1 问题描述 155
7.6.2 动态规划法求解 155
7.6.3 0/1背包问题算法框架 157
7.6.4 0/1背包问题算法 160
7.6.5 性能分析 162
7.6.6 使
第1章 算法问题求解基础 1
1.1 算法概述 1
1.1.1 什么是算法 1
1.1.2 为什么学习算法 3
1.2 问题求解方法 3
1.2.1 问题和问题求解 4
1.2.2 问题求解过程 4
1.2.3 软件生命周期 5
1.3 算法设计与分析 5
1.3.1 算法问题求解过程 5
1.3.2 如何设计算法 6
1.3.3 如何表示算法 6
1.3.4 如何确认算法 6
1.3.5 如何分析算法 7
1.4 递归和归纳 7
1.4.1 递归 7
1.4.2 递归算法示例 9
1.4.3 归纳证明 11
习题1 13
第2章 算法分析基础 14
2.1 算法复杂度 14
2.1.1 什么是好的算法 14
2.1.2 影响程序执行时间的因素 15
2.1.3 算法的时间复杂度 16
2.1.4 使用程序步分析算法 17
2.1.5 算法的空间复杂度 18
2.2 渐近表示法 19
2.2.1 大O记号 19
2.2.2 Ω记号 20
2.2.3 Θ记号 21
2.2.4 小o记号 21
2.2.5 算法按时间复杂度分类 21
2.3 递推关系 22
2.3.1 递推方程 22
2.3.2 替换方法 23
2.3.3 迭代方法 23
2.3.4 递归树 23
2.3.5 主方法 25
2.4 分摊分析 25
2.4.1 聚集分析 26
2.4.2 会计方法 26
2.4.3 势能方法 27
习题2 28
第3章 伸展树与跳表 31
3.1 伸展树 31
3.1.1 二叉搜索树 31
3.1.2 自调节树和伸展树 31
3.1.3 伸展操作 32
3.1.4 伸展树类 34
3.1.5 旋转的实现 34
3.1.6 插入运算的实现 35
3.1.7 分摊分析 37
3.2 跳表 39
3.2.1 什么是跳表 39
3.2.2 跳表类 40
3.2.3 层次分配 42
3.2.4 插入运算的实现 43
3.2.5 性能分析 44
习题3 45
第2部分 算法设计策略
第4章 基本搜索和遍历方法 46
4.1 基本概念 46
4.2 图的搜索和遍历 47
4.2.1 搜索方法 47
4.2.2 邻接表类 48
4.2.3 广度优先搜索 49
4.2.4 深度优先搜索 51
4.3 双连通分量 53
4.3.1 基本概念 53
4.3.2 发现关节点 54
4.3.3 构造双连通图 58
4.4 与或图 58
4.4.1 问题分解 58
4.4.2 判断与或树是否可解 60
4.4.3 构建解树 61
4.5 区间最值查询（RMQ） 62
4.5.1 区间信息维护与查询 62
4.5.2 ST算法求解RMQ问题 63
4.6 最近公共祖先（LCA） 65
4.6.1 概述 65
4.6.2 倍增法求解LCA问题 66
4.6.3 在线RMQ法求解LCA问题 68
4.6.4 Tarjan算法求解LCA问题 70
习题4 73
第5章 分治法 75
5.1 一般方法 75
5.1.1 分治法的基本思想 75
5.1.2 算法分析 76
5.1.3 数据结构 77
5.2 求最大、最小元 78
5.2.1 分治法求解 78
5.2.2 时间分析 79
5.3 二分搜索 80
5.3.1 分治法求解 80
5.3.2 对半搜索 81
5.3.3 二叉判定树 82
5.3.4 搜索算法的时间下界 84
5.4 排序问题 85
5.4.1 合并排序 85
5.4.2 快速排序 87
5.4.3 排序算法的时间下界 91
5.5 选择问题 92
5.5.1 分治法求解 92
5.5.2 随机选择主元 93
5.5.3 线性时间选择算法 94
5.5.4 时间分析 96
5.5.5 允许重复元素的选择算法 97
5.6 斯特拉森矩阵乘法 97
5.6.1 分治法求解 97
5.6.2 斯特拉森矩阵乘法简介 98
习题5 99
第6章 贪心法 102
6.1 一般方法 102
6.2 背包问题 103
6.2.1 问题描述 103
6.2.2 贪心法求解 104
6.2.3 算法正确性 105
6.3 带时限的作业排序问题 106
6.3.1 问题描述 106
6.3.2 贪心法求解 107
6.3.3 算法正确性 108
6.3.4 可行性判定 108
6.3.5 作业排序贪心算法 109
6.3.6 改进算法 110
6.4 最佳合并模式 112
6.4.1 问题描述 113
6.4.2 贪心法求解 113
6.4.3 算法正确性 115
6.5 最小代价生成树 116
6.5.1 问题描述 116
6.5.2 贪心法求解 116
6.5.3 普里姆算法 117
6.5.4 克鲁斯卡尔算法 119
6.5.5 算法正确性 121
6.6 单源最短路径 122
6.6.1 问题描述 122
6.6.2 贪心法求解 122
6.6.3 迪杰斯特拉算法 123
6.6.4 算法正确性 125
6.7 磁带最优存储 127
6.7.1 单带最优存储 127
6.7.2 多带最优存储 128
6.8 贪心法的基本要素 129
6.8.1 最优量度标准 129
6.8.2 最优子结构 129
习题6 130
第7章 动态规划法 133
7.1 一般方法和基本要素 133
7.1.1 一般方法 133
7.1.2 基本要素 134
7.1.3 多段图问题 134
7.1.4 资源分配问题 137
7.1.5 关键路径问题 138
7.2 每对结点间的最短路径 140
7.2.1 问题描述 140
7.2.2 动态规划法求解 140
7.2.3 弗洛伊德算法 141
7.2.4 算法正确性 143
7.3 矩阵连乘 143
7.3.1 问题描述 143
7.3.2 动态规划法求解 144
7.3.3 矩阵连乘算法 145
7.3.4 备忘录方法 147
7.4 最长公共子序列 147
7.4.1 问题描述 147
7.4.2 动态规划法求解 148
7.4.3 最长公共子序列算法 149
7.4.4 改进算法 151
7.5 最优二叉搜索树 151
7.5.1 问题描述 151
7.5.2 动态规划法求解 151
7.5.3 最优二叉搜索树算法 153
7.6 0/1背包问题 155
7.6.1 问题描述 155
7.6.2 动态规划法求解 155
7.6.3 0/1背包问题算法框架 157
7.6.4 0/1背包问题算法 160
7.6.5 性能分析 162
7.6.6 使
