算法设计与分析(第2版高等学校计算机专业系列教材)

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

黄宇，南京大学计算机科学与技术系教授，博士生导师，主要研究方向为分布式算法、分布式系统和软件方法学。曾主持两项国家自然科学基金项目，并作为主要成员参与了国家973计划、国家自然科学基金创新群体项目等多项国家重大科研项目。2014年获得南京大学登峰人才支持计划资助，2011年获 技术发明奖。所指导的博士论文荣获2016年中国计算机学会博士学位论文奖。已在IEEE Trans. on Computers、IEEE Trans. on Parallel and Distributed Systems、IEEE PerCom等重要国际期刊及会议上发表多篇论文。

前言 教学建议 第一部分计算模型 第1 章抽象的算法设计与分析........... 2 1.1 RAM 模型的引入................... 2 1.1.1 计算的基本概念................... 2 1.1.2计算模型的基本概念. . . . . . . .. .. . . . . 3 1.1.3RAM 模型........................ 3 1.1.4计算模型的选择：易用性与精确性........................... 5 1.2 抽象算法设计...................... 6 1.2.1 算法问题规约..................... 6 1.2.2 算法正确性证明：数学归纳法....... 7 1.3 抽象算法分析...................... 8 1.3.1 抽象算法的性能指标. . . . . . . .. .. . . . . 8 1.3.2 最坏情况时间复杂度分析.......... 9 1.3.3 平均情况时间复杂度分析......... 10 1.4 习题. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 11 第2 章从算法的视角重新审视数学的概念. . . . . . . . . . .. .. .. .. . . . . 14 2.1 数学运算背后的算法操作......... 14 2.1.1 取整. x . 和. x . . . . . . . . . . .. .. .. .. . 14 2.1.2 对数log n . . . . .. .. .. . . . . . . . . . .. .. . 14 2.1.3 阶乘n!. . . . .. .. .. .. . . . . . . . . . .. .. . 15 2.1.4 常用级数求和.f (i). . . . . . .. .. .. .. 16 2.1.5 期望E[X] ....................... 18 2.2 函数的渐近增长率................ 19 2.3 “分治递归”求解................. 21 2.3.1 替换法. .. .. . . . . . . . . . .. .. .. .. . . . . 21 2.3.2 分治递归与递归树.. . . . . . . . . . .. .. .21 2.3.3 Master 定理. .. .. .. . . . . . . . . . .. .. .. 22 2.4 习题. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 23 第二部分从蛮力到分治 第3 章蛮力算法设计................... 31 3.1 蛮力选择与查找. . . . . . .. .. .. . . . . . . . 31 3.2 蛮力排序.. . . . . . .. .. .. .. . . . . . . . . . .. 32 3.2.1选择排序. . . .. .. .. .. . . . . . . . . . .. .. 32 3.2.2插入排序. . . .. .. .. .. . . . . . . . . . .. .. 33 3.3 习题. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 35 第4 章分治排序.. .. .. .. . . . . . .. .. .. .. . . . 37 4.1 快速排序. . . . . . . .. .. .. .. . . . . . . . . . .. 37 4.1.1插入排序的不足. .. .. . . . . . . . . . .. .. 37 4.1.2快速排序的改进. .. .. . . . . . . . . . .. .. 38 4.1.3最坏情况时间复杂度分析......... 39 4.1.4基于递归方程的平均情况时间复杂度分析. . . . . . .. .. .. . . . . . . . . . . 40 4.1.5基于指标随机变量的平均情况时间复杂度分析. . . . . . .. .. .. . . . . . . . . . . 41 4.2 合并排序.. . . . . . .. .. .. .. . . . . . . . . . .. 43 4.3 基于比较的排序的下界. .. .. .. . . . . . 44 4.3.1决策树的引入. . . . . . .. .. .. . . . . . . . . 45 4.3.2比较排序的最坏情况时间复杂度的下界. . . . . .. .. .. .. . . . . . . . .. .. .. 45 4.3.3比较排序的平均情况时间复杂度的下界. . . . . .. .. .. .. . . . . . . . .. .. .. 46 4.4 习题. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 48 第5 章线性时间选择................... 50 5.1 期望线性时间选择................ 50 5.1.1选择算法设计. . . . . . .. .. .. . . . . . . . . 50 5.1.2选择算法分析. . . . . . .. .. .. . . . . . . . . 51 5.2 最坏情况线性时间选择. .. .. .. . . . . . 52 5.2.1选择算法设计. . . . . . .. .. .. . . . . . . . . 52 5.2.2选择算法分析. .. . . . . . . . . . .. .. . . . . 53 5.3 习题. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 54 第6 章对数时间查找................... 57 6.1 折半查找.. .. . . . . . . . .. .. .. .. . . . . . . . 57 6.1.1经典折半查找. .. . . . . . . . .. .. .. . . . . 57 6.1.2查找峰值. . . . . . . .. .. .. . . . . . . . . . .. 58 6.1.3计算√N ........................ 59 6.2 平衡二叉搜索树. . . . . . . . .. .. .. . . . . . 59 6.2.1二叉搜索树及其平衡性........... 59 6.2.2红黑树的定义. .. . . . . . . . . . .. .. . . . . 60 6.2.3红黑树的平衡性. .. .. .. .. . . . . . . . . . 62 6.3 习题. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 62 第7 章分治算法设计要素. . . . . . . . . . .. .. .65 7.1 分治算法的关键特征. . . . . . . .. .. .. . 65 7.2 计算逆序对的个数................ 66 7.2.1依托于合并排序的逆序对计数.. .. . 66 7.2.2原地的逆序对计数.. .. . . . . . . . . . .. .67 7.3 整数乘法.. .. . . . . . . . .. .. .. .. . . . . . . . 68 7.3.1简单分治. . . . . . . .. .. .. . . . . . . . . . .. 69 7.3.2更精细的分治. .. . . . . . .. .. .. .. . . . . 69 7.4 芯片检测.. .. . . . . . . . .. .. .. .. . . . . . . . 70 7.5 习题. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 71 第三部分从图遍历到图优化 第8 章图的深度优先遍历. . . . . . . . . . .. .. .76 8.1 图和图遍历. . . . . . . .. .. .. .. . . . . . . . . . 76 8.2 有向图上的深度优先遍历......... 77 8.2.1遍历框架. . . . . . . .. .. .. . . . . . . . . . .. 77 8.2.2深度优先遍历树. .. .. .. .. . . . . . . . . . 79 8.2.3活动区间. . . . . . . .. .. .. . . . . . . . . . .. 79 8.3 有向图上深度优先遍历的应用.. .. .82 8.3.1拓扑排序. . . . . . . .. .. .. . . . . . . . . . .. 82 8.3.2关键路径. . . . . . . .. .. .. . . . . . . . . . .. 85 8.3.3有向图中的强连通片............. 87 8.4 无向图上的深度优先遍历......... 91 8.4.1无向图的深度优先遍历树......... 91 8.4.2无向图的深度优先遍历框架....... 92 8.5 无向图上深度优先遍历的应用.. .. .93 8.5.1容错连通. . . .. .. .. .. . . . . . . . . . .. .. 93 8.5.2寻找割点. . . .. .. .. .. . . . . . . . . . .. .. 94 8.5.3寻找桥. . . . . . . . . . .. .. .. .. . . . . . . . . 96 8.6 习题. . . . . . . . . . .. .. .. . . . . . . . .. .. .. .. 97 第9 章图的广度优先遍历............. 102 9.1 广度优先遍历. . . . . . . .. .. .. .. . . . . . 102 9.1.1广度优先遍历框架.............. 103 9.1.2有向图的广度优先遍历树. . . . . . . . 105 9.1.3无向图的广度优先遍历树. . . . . . . . 106 9.2 广度优先遍历的应用. . . . .. .. .. . . . 107 9.2.1判断二分图. .. . . . . . . . . . .. .. .. .. . 107 9.2.2寻找k 度子图.. .. .. . . . . . . . .. .. .. 108 9.3 习题. . . . . . . . . .. .. .. . . . . . . . . . .. .. .. 109 第10 章图优化问题的贪心求解. . . . . . ..111 10.1最小生成树问题与给定源点最短路径问题. . . . .. .. .. . . . . . . . . . 111 10.2Prim 算法. .. . . . . . . . .. .. .. . . . . . . . .112 10.2.1Prim 算法的正确性. .. . . . . . . . . . . 113 10.2.2Prim 算法的实现. . . . . . .. .. .. . . . 116 10.2.3Prim 算法的分析. . . . . . .. .. .. . . . 117 10.3Kruskal 算法. . . . . . . . . .. .. .. .. . . . . 118 10.3.1Kruskal 算法的正确性. . . . . . . . . . .119 10.3.2Kruskal 算法的实现与分析...... 120 10.4最小生成树贪心构建框架MCE. . . . . . . . . . .. .. .. . . . . . . . . . .. ..120 10.4.1从MCE 框架的角度分析Prim 算法..................... 121 10.4.2从MCE 框架的角度分析Kruskal 算法. .. . . . . . . . . . .. .. .. . 122 10.5Dijkstra 算法. .. .. . . . . . . . . . .. .. .. . 123 10.5.1Dijkstra 算法的设计.. . . . . . . . . . ..123 10.5.2Dijkstra 算法的正确性证明与性能分析. .. . . . . . . . . . .. .. .. .. . . 125 10.6贪心遍历框架BestFS. .. .. .. . . . . . 126 10.7 习题. . . . . . . . . .. .. . . . . . . . . . .. .. .. .128 第11 章贪心算法设计要素............ 134 11.1贪心算法的基本结构. . .. .. .. .. . . 134 11.2相容任务调度问题.............. 134 11.2.1直觉的尝试. . . .. .. .. . . . . . . . . . .. 135 11.2.2基于任务结束时间的贪心算法. . . 135 11.3Hu.man 编码.. .. .. . . . . . . . .. .. .. . 136 11.3.1可变长度编码.. . . . . . . . . . .. .. .. .136 11.3.2最优编码方案的性质........... 137 11.3.3贪心的Hu.man 编码........... 139 11.4 习题.. .. . . . . . . . .. .. .. . . . . . . . . . .. .139 第12 章图优化问题的动态规划求解. . . 142 12.1有向无环图上的给定源点最短路径问题. . . . . . . . .. .. . . . . . . . 142 12.2所有点对最短路径问题......... 143 12.2.1传递闭包问题和Shortcut 算法... 143 12.2.2所有点对最短路径：基于路径长度的递归........... 145 12.2.3Floyd-Warshall 算法：基于中继节点范围的递归. . . . . . . 146 12.3 习题.. .. . . . . . . . . . .. .. . . . . . . . . . .. .147 第13 章动态规划算法设计要素. . . . . . . .150 13.1动态规划的动机. . . . . . . .. .. .. . . . . 150 13.2动态规划的引入. . . . . . . .. .. .. . . . . 151 13.2.1基于朴素遍历的递归........... 152 13.2.2未做规划的递归............... 152 13.2.3采用动态规划的递归........... 153 13.3动态规划的关键特征. . . . . . .. .. .. 155 13.4动态规划应用举例.............. 156 13.4.1编辑距离问题.. . . . . . . . . . .. .. .. .156 13.4.2硬币兑换问题.. . . . . . . . . . .. .. .. .158 13.4.3最大和连续子序列问题......... 159 13.4.4相容任务调度问题............. 160 13.5习题.. .. . . . . . .. .. .. .. . . . . . . . . . .. .161 第四部分围绕数据结构的算法设计 第14 章堆与偏序关系.. .. .. .. . . . . . . . . . 168 14.1堆的定义. .. . . . . . . . .. .. .. .. . . . . . . 168 14.2堆的抽象维护.. . . . . . . . . . .. .. .. . . 168 14.2.1堆的修复. . . . . . . . .. .. .. .. . . . . . . 169 14.2.2堆的构建. . . . .. .. .. .. . . . . . . . . . . 169 14.3堆的具体实现. . . . . . . . . .. .. .. . . . . 171 14.4堆的应用. . . . . . .. .. .. .. . . . . . . . . . . 172 14.4.1堆排序.. .. .. . . . . . . . . . .. .. . . . . . 172 14.4.2基于堆实现优先队列........... 173 14.5 习题. . . . . . . .. .. .. . . . . . . . . . .. .. .. .174 第15 章并查集与动态等价关系. . . . . . ..176 15.1动态等价关系. . . . . . . . . .. .. . . . . . . 176 15.2基于根树的基础实现：普通“并”+普通“查”. .. .. .. . . .177 15.3保证合并的平衡性：加权“并”+普通“查”. .. .. .. . . .178 15.4降低查找的代价：加权“并”+路径压缩“查”.. .. . 179 15.5 习题. . . . . . . . . .. .. . . . . . . . . . .. .. .. .180 第16 章哈希表与查找.. .. . . . . . . . . . .. .. 182 16.1直接寻址表：查找表的蛮力实现. .. .. . . . . . . . . . .. .. .. ..182 16.2哈希表的基本原理.............. 183 16.3封闭寻址冲突消解.............. 183 16.4开放寻址冲突消解.............. 185 16.5 习题. . . . . . . . . .. .. . . . . . . . . . .. .. .. .188 第17 章有限自动机与串匹配. .. . . . . . . . 189 17.1蛮力串匹配..................... 189 17.2基于有限自动机的串匹配. . . . . .. 190 17.3从有限自动机的角度理解KMP 算法....................... 191 17.3.1对传统匹配自动机的改进.. . . . . . 191 17.3.2自动机构建的原理............. 192 17.3.3KMP 算法的实现.. .. . . . . . .. .. .. 193 17.4习题. . . . . . . . . .. .. . . . . . . . . . .. .. .. .194 第五部分算法分析进阶 第18 章平摊分析. .. . . . . . . . . . .. .. .. .. . . 198 18.1平摊分析的动机. . . .. .. .. .. . . . . . . 198 18.2平摊分析的基本过程. . .. .. .. .. . . 199 18.3MultiPop 栈. . . . . . . . .. .. .. . . . . . . . . 200 18.4 数组扩充. . . . . . . . . . .. .. .. .. . . . . . . 201 18.5 二进制计数器.. . . . . . . . . . .. .. .. . . 202 18.6 基于栈实现队列. . . . . . . .. .. .. . . . . 203 18.7 习题.. .. . . . . . . . . . .. .. . . . . . . . . . .. .204 第19 章对手论证. .. .. .. . . . . . . . . . .. .. .. 207 19.1 对手论证的基本形式. . . . . . . . .. .. 207 19.2 选择最大或最小元素. . . . . . .. .. .. 207 19.3 同时选择最大和最小元素. . . . . . . 208 19.4 选择次大元素.. . . . . . . . . . .. .. .. . . 209 19.5 选择中位数..................... 211 19.6 习题.. .. . . . . . . . .. .. .. . . . . . . . . . .. .212 第六部分计算复杂性初步 第20 章问题与归约................... 216 20.1 NP 问题. . . . . . . . . . .. .. .. .. . . . . . . . 216 20.1.1 优化问题和判定问题........... 216 20.1.2 P 问题的定义. . . . . . . . . .. .. .. .. . 216 20.1.3 NP 问题的定义. .. .. .. .. . . . . . . . .217 20.2 问题间的归约. . . . . . . .. .. .. . . . . . . 218 20.2.1 归约的定义. .. .. . . . . . . . . . .. .. .. 218 20.2.2 归约的代价与问题难度的比较. .. 219 20.3 习题. . . . . . . .. .. .. . . . . . . . . . .. .. .. .219 第21 章NP 完全性理论初步.. .. .. .. . . . 221 21.1 NP 完全问题的定义. . . . .. .. .. . . . 221 21.2 NP 完全性证明的初步知识. . . .. . 222 21.2.1 一般问题和特例问题........... 222 21.2.2 等价问题. . . . .. .. .. .. . . . . . . . . . . 223 21.3 习题. . . . . . . .. .. .. . . . . . . . . . .. .. .. .224 附录A 数学归纳法. .. .. . . . . . . . . . .. .. .. . 226 附录B 二叉树. . . . . . . . .. .. .. . . . . . . . . . .. .227 参考文献................................ 228