算法设计与分析 第2版

✍ Scribed by 黄宇

• Publisher: 机械工业出版社
• Year: 2020
• Tongue: Chinese
• Leaves: 238
• Edition: 2
• Category: Library

✦ Synopsis

本书是作者在多年从事算法设计与分析课程教学和研究的基础上编写而成，系统地介绍了算法设计与分析的理论、方法和技术。内容围绕两条主线来组织。一条主线是介绍典范性的算法问题，如排序、选择、图遍历等。 另一条主线是介绍典范性的算法设计分析策略，如分治、贪心、动态规划等算法设计策略和对手分析、平摊分析等算法分析策略。本书中两条主线交替进行，每条主线又各自分为基本和进阶两部分。

已附上书签

✦ Table of Contents

目录
第一部分 计算模型
第1章 抽象的算法设计与分析
1.1 RAM模型的引入
1.1.1 计算的基本概念
1.1.2 计算模型的基本概念
1.1.3 RAM模型
1.1.4 计算模型的选择：易用性与精确性
1.2 抽象算法设计
1.2.1 算法问题规约
1.2.2 算法正确性证明：数学归纳法
1.3 抽象算法分析
1.3.1 抽象算法的性能指标
1.3.2 最坏情况时间复杂度分析
1.3.3 平均情况时间复杂度分析
1.4 习题
第2章 从算法的视角重新审视数学的概念
2.1 数学运算背后的算法操作
2.1.1 取整［x ］和［x］
2.1.2 对数logn
2.1.3 阶乘n!
2.1.4 常用级数求和∑f（i）
2.1.5 期望E［X］
2.2 函数的渐近增长率
2.3 “分治递归”求解
2.3.1 替换法
2.3.2 分治递归与递归树
2.3.3 Master定理
2.4 习题
第二部分 从蛮力到分治
第3章 蛮力算法设计
3.1 蛮力选择与查找
3.2 蛮力排序
3.2.1 选择排序
3.2.2 插入排序
3.3 习题
第4章 分治排序
4.1 快速排序
4.1.1 插入排序的不足
4.1.2 快速排序的改进
4.1.3 最坏情况时间复杂度分析
4.1.4 基于递归方程的平均情况时间复杂度分析
4.1.5 基于指标随机变量的平均情况时间复杂度分析
4.2 合并排序
4.3 基于比较的排序的下界
4.3.1 决策树的引入
4.3.2 比较排序的最坏情况时间复杂度的下界
4.3.3 比较排序的平均情况时间复杂度的下界
4.4 习题
第5章 线性时间选择
5.1 期望线性时间选择
5.1.1 选择算法设计
5.1.2 选择算法分析
5.2 最坏情况线性时间选择
5.2.1 选择算法设计
5.2.2 选择算法分析
5.3 习题
第6章 对数时间查找
6.1 折半查找
6.1.1 经典折半查找
6.1.2 查找峰值
6.1.3 计算？
6.2 平衡二叉搜索树
6.2.1 二叉搜索树及其平衡性
6.2.2 红黑树的定义
6.2.3 红黑树的平衡性
6.3 习题
第7章 分治算法设计要素
7.1 分治算法的关键特征
7.2 计算逆序对的个数
7.2.1 依托于合并排序的逆序对计数
7.2.2 原地的逆序对计数
7.3 整数乘法
7.3.1 简单分治
7.3.2 更精细的分治
7.4 芯片检测
7.5 习题
第三部分 从图遍历到图优化
第8章 图的深度优先遍历
8.1 图和图遍历
8.2 有向图上的深度优先遍历
8.2.1 遍历框架
8.2.2 深度优先遍历树
8.2.3 活动区间
8.3 有向图上深度优先遍历的应用
8.3.1 拓扑排序
8.3.2 关键路径
8.3.3 有向图中的强连通片
8.4 无向图上的深度优先遍历
8.4.1 无向图的深度优先遍历树
8.4.2 无向图的深度优先遍历框架
8.5 无向图上深度优先遍历的应用
8.5.1 容错连通
8.5.2 寻找割点
8.5.3 寻找桥
8.6 习题
第9章 图的广度优先遍历
9.1 广度优先遍历
9.1.1 广度优先遍历框架
9.1.2 有向图的广度优先遍历树
9.1.3 无向图的广度优先遍历树
9.2 广度优先遍历的应用
9.2.1 判断二分图
9.2.2 寻找k度子图
9.3 习题
第10章 图优化问题的贪心求解
10.1 最小生成树问题与给定源点最短路径问题
10.2 Prim算法
10.2.1 Prim算法的正确性
10.2.2 Prim算法的实现
10.2.3 Prim算法的分析
10.3 Kruskal算法
10.3.1 Kruskal算法的正确性
10.3.2 Kruskal算法的实现与分析
10.4 最小生成树贪心构建框架 MCE
10.4.1 从MCE框架的角度分析Prim算法
10.4.2 从MCE框架的角度分析Kruskal算法
10.5 Dijkstra算法
10.5.1 Dijkstra算法的设计
10.5.2 Dijkstra算法的正确性证明与性能分析
10.6 贪心遍历框架BestFS
10.7 习题
第11章 贪心算法设计要素
11.1 贪心算法的基本结构
11.2 相容任务调度问题
11.2.1 直觉的尝试
11.2.2 基于任务结束时间的贪心算法
11.3 Huffman编码
11.3.1 可变长度编码
11.3.2 最优编码方案的性质
11.3.3 贪心的Huffman编码
11.4 习题
第12章 图优化问题的动态规划求解
12.1 有向无环图上的给定源点最短路径问题
12.2 所有点对最短路径问题
12.2.1 传递闭包问题和Shortcut算法
12.2.2 所有点对最短路径：基于路径长度的递归
12.2.3 Floyd-Warshall算法：基于中继节点范围的递归
12.3 习题
第13章 动态规划算法设计要素
13.1 动态规划的动机
13.2 动态规划的引入
13.2.1 基于朴素遍历的递归
13.2.2 未做规划的递归
13.2.3 采用动态规划的递归
13.3 动态规划的关键特征
13.4 动态规划应用举例
13.4.1 编辑距离问题
13.4.2 硬币兑换问题
13.4.3 最大和连续子序列问题
13.4.4 相容任务调度问题
13.5 习题
第四部分 围绕数据结构的算法设计
第14章 堆与偏序关系
14.1 堆的定义
14.2 堆的抽象维护
14.2.1 堆的修复
14.2.2 堆的构建
14.3 堆的具体实现
14.4 堆的应用
14.4.1 堆排序
14.4.2 基于堆实现优先队列
14.5 习题
第15章 并查集与动态等价关系
15.1 动态等价关系
15.2 基于根树的基础实现：普通“并”＋普通“查”
15.3 保证合并的平衡性：加权“并”＋普通“查”
15.4 降低查找的代价：加权“并”＋路径压缩“查”
15.5 习题
第16章 哈希表与查找
16.1 直接寻址表：查找表的蛮力实现
16.2 哈希表的基本原理
16.3 封闭寻址冲突消解
16.4 开放寻址冲突消解
16.5 习题
第17章 有限自动机与串匹配
17.1 蛮力串匹配
17.2 基于有限自动机的串匹配
17.3 从有限自动机的角度理解KMP算法
17.3.1 对传统匹配自动机的改进
17.3.2 自动机构建的原理
17.3.3 KMP算法的实现
17.4 习题
第五部分 算法分析进阶
第18章 平摊分析
18.1 平摊分析的动机
18.2 平摊分析的基本过程
18.3 MultiPop栈
18.4 数组扩充
18.5 二进制计数器
18.6 基于栈实现队列
18.7 习题
第19章 对手论证
19.1 对手论证的基本形式
19.2 选择最大或最小元素
19.3 同时选择最大和最小元素
19.4 选择次大元素
19.5 选择中位数
19.6 习题
第六部分 计算复杂性初步
第20章 问题与归约
20.1 NP问题
20.1.1 优化问题和判定问题
20.1.2 P问题的定义
20.1.3 NP问题的定义
20.2 问题间的归约
20.2.1 归约的定义
20.2.2 归约的代价与问题难度的比较
20.3 习题
第21章 NP完全性理论初步
21.1 NP完全问题的定义
21.2 NP完全性证明的初步知识
21.2.1 一般问题和特例问题
21.2.2 等价问题
21.3 习题
附录A数学归纳法
附录B二叉树
参考文献