本书是作者在多年从事算法设计与分析课程教学和研究的基础上编写而成，系统地介绍了算法设计与分析的理论、方法和技术。内容围绕两条主线来组织。一条主线是介绍典范性的算法问题，如排序、选择、图遍历等。 另一条主线是介绍典范性的算法设计分析策略，如分治、贪心、动态规划等算法设计策略和对手分析、平摊分析等算法分析策略。本书中两条主线交替进行，每条主线又各自分为基本和进阶两部分。
无
算法是计算的灵魂（spirit of computing），而算法设计与分析的基础知识是计算机科学的基石。算法设计与分析的内容很丰富，可以从不同视角进行组织与阐述。一种视角是关注经典的算法问题，如排序、选择、查找、图遍历等；另一种视角是关注经典的算法设计策略，如分治、贪心、动态规划等。
根据这一“二维视角”，本书的核心内容分为四块，如图1 所示。从问题的视角看，主要有两类问题。第一类为序相关的问题，包括基于比较的排序、选择与查找；第二类为图相关的问题，包括基本的图遍历问题以及最小生成树、最短路径等图优化问题。从策略的视角看，主要有两类策略。第一类为遍历策略，包括线性表上的遍历和图上的遍历；第二类为优化策略，在序相关的问题上主要体现为分治策略，在图相关的问题上体现为贪心策略与动态规划策略。
图1 二维视角下的核心内容
上述核心内容是算法设计与分析中最基础的知识与最典型的技术。以此为基础，本书进一步讨论更深入的算法设计与分析技术。一类是围绕经典数据结构的算法设计与分析，另一类是进阶的算法分析策略。此外，本书集中讨论抽象的—— 与机器、实现语言无关的—— 算法设计与分析。为此，在主体内容之前，本书首先讲解计算模型的基础知识，它是后续抽象的算法设计与分析的基础。本书的最后介绍计算复杂性的基础知识，试图让读者在了解各类算法问题、学习各种算法设计与分析技术之后，对算法问题的难度有一个总体的认识。本书内容的总体结构如图2所示。
本书的内容是作者在多年授课的过程中逐渐积淀而成的，因而它不是对算法设计与分析知识的一个百科全书式的覆盖，而是对一些重点内容更专注的讨论。本书的内容和组织方式是面向一个学期的授课而设计的。在授课形式方面，我们将课程分为主课与辅课两种形式。主课主要围绕典型的问题、经典的算法展开，而辅课则主要围绕算法策略展开。若干次的主课讲授形成一个阶段，每一个阶段结束后，通过一次辅课从策略的视角回顾最近阶段的一组算法，同时补充新的素材对相应的策略进行进一步的讨论。
图2 本书内容总体结构
在知识讲授之外，实践也是算法设计与分析课程的重要组成部分。算法课程的实践分为两类。一类是传统的习题。本书习题大体按照这样的顺序给出：首先是紧扣书本知识的习题，例如一些简单定理的证明、紧扣算法细节的一些问题等；其次是应用题，它需要读者对一个具有一定现实意义的问题进行建模，并用书中的算法知识来解决问题。另一类是编程实现题。本书的应用题大都可以用于算法编程实现的训练。在实际授课中，我们挑选了部分应用题作为编程实现题，并基于开源的OnlineJudge 平台进行自动评测，取得了良好的效果。
本书的素材主要源自南京大学计算机系本科生“算法设计与分析”课程的授课内容。其中一部分素材来源于共同授课的其他老师，包括前期负责讲授主课并指导辅课教学的陈道蓄老师，以及后期共同分班讲授这门课程的钱柱中、张胜、徐经纬老师。还有一部分素材来源于经典的算法教科书和国外大学的授课教师在其课程网站上发布的课程材料。另外，还要感谢“算法设计与分析”课程早期的两位助教魏恒峰和杨怡玲，他们对大量的课程资料进行了整理与提炼。最后要感谢上过这门课的学生，他们创造性的提问与解题时所犯的错误为本书提供了宝贵的素材。
计算机\算法
本书源于作者多年讲授“算法设计与分析”课程的教学实践和经验积淀，主要面向计算机专业本科生，以及其他需要学习计算机科学基本知识与了解计算机程序设计背后原理的读者。
本书特色
内容定位科学。本书定位于讲解抽象的——与机器、实现语言无关的——算法设计与分析知识。这一定位有助于读者脱离具体的机器与编程语言的细节，了解算法设计背后的核心原理。
内容组织合理。本书的内容组织兼顾问题和策略两个维度，通过排序、选择、查找、图遍历、图优化等经典算法问题的逐步深入求解，来展示遍历、分治、贪心、动态规划等经典策略的运用。本书内容具有“自包含”特色，读者只需要具有离散数学的基础知识，以及计算机程序设计的入门知识，即可进行学习。
习题资源丰富。本书为每章内容配备了丰富的习题。习题由浅入深，涵盖了主要知识点，其中部分习题改编自授课过程中学生常犯的典型错误示例。大部分习题不仅可以布置为书面习题，也易于配以输入输出数据，用作在线评测试题。
作者简介
黄宇，南京大学计算机科学与技术系教授，博士生导师，主要研究方向为分布式算法、分布式系统、系统软件。曾主持三项国家自然科学基金，并作为主要成员参与了国家973计划、国家自然科学基金创新群体项目等多项国家重大科研项目。2014年获得南京大学登峰人才支持计划资助，联合指导的博士论文分别获得2016年、2017年中国计算机学会优秀博士学位论文奖。已在ACM PODC、IEEE SRDS、IEEE Trans.on Computers、IEEE Trans.on Parallel and Distributed Systems等重要国际会议、期刊上发表多篇论文。
在教学方面的成就：曾入选2018年度国家“高校计算机专业优秀教师奖励计划”，获得2018年度南京大学“刘厚俊奖教金”；所教授的算法课程入选2019年度“南京大学百层次优质课程”，并被评为2019年度计算机系毕业生“我心目中的好课程”。
黄宇 编著：
黄宇，南京大学计算机科学与技术系教授，博士生导师，主要研究方向为分布式算法、分布式系统和软件方法学。曾主持两项国家自然科学基金项目，并作为主要成员参与了国家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.3 RAM 模型........................ 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.2 Prim 算法. .. . . . . . . . .. .. .. . . . . . . . .112
10.2.1 Prim 算法的正确性. .. . . . . . . . . . . 113
10.2.2 Prim 算法的实现. . . . . . .. .. .. . . . 116
10.2.3 Prim 算法的分析. . . . . . .. .. .. . . . 117
10.3 Kruskal 算法. . . . . . . . . .. .. .. .. . . . . 118
10.3.1 Kruskal 算法的正确性. . . . . . . . . . .119
10.3.2 Kruskal 算法的实现与分析...... 120
10.4 最小生成树贪心构建框架MCE. . . . . . . . . . .. .. .. . . . . . . . . . .. ..120
10.4.1 从MCE 框架的角度分析Prim 算法..................... 121
10.4.2 从MCE 框架的角度分析Kruskal 算法. .. . . . . . . . . . .. .. .. . 122
10.5 Dijkstra 算法. .. .. . . . . . . . . . .. .. .. . 123
10.5.1 Dijkstra 算法的设计.. . . . . . . . . . ..123
10.5.2 Dijkstra 算法的正确性证明与性能分析. .. . . . . . . . . . .. .. .. .. . . 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.3 Hu.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.3 Floyd-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.3 KMP 算法的实现.. .. . . . . . .. .. .. 193
17.4 习题. . . . . . . . . .. .. . . . . . . . . . .. .. .. .194
第五部分算法分析进阶
第18 章平摊分析. .. . . . . . . . . . .. .. .. .. . . 198
18.1 平摊分析的动机. . . .. .. .. .. . . . . . . 198
18.2 平摊分析的基本过程. . .. .. .. .. . . 199
18.3 MultiPop 栈. . . . . . . . .. .. .. . . . . . . . . 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
