算法设计与分析

本书讲授算法设计与分析的基础知识。首先介绍计算模型的基本概念；其次围绕遍历、分治、贪心、动态规划这四个经典算法设计策略，讲解了排序、选择、查找、图遍历、小生成树、短路径等经典算法问题；后介绍了计算复杂性的基础知识。本书主要面向计算机专业本科生，以及其他需要学习计算机科学基础知识与了解计算机程序设计背后原理的读者。

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

前言
教学建议
第一部分计算模型
第1章抽象的算法设计与分析2
1.1RAM模型的引入2
1.1.1计算的基本概念2
1.1.2计算模型的基本概念3
1.1.3RAM模型4
1.1.4计算模型的选择：易用性和精确性6
1.2抽象算法设计7
1.2.1算法问题规约7
1.2.2算法正确性证明：数学归纳法8
1.3抽象算法分析10
1.3.1抽象算法的性能指标10
1.3.2最坏情况时间复杂度分析11
1.3.3平均情况时间复杂度分析12
1.4习题13
第2章从算法的视角重新审视数学的概念16
2.1数学运算背后的算法操作16
2.1.1取整x和x16
2.1.2对数logn17
2.1.3阶乘n！18
2.1.4常见级数求和∑ni=1f（i）19
2.1.5期望E（X）20
2.2函数的渐近增长率22
2.3“分治递归”求解24
2.3.1替换法24
2.3.2分治递归与递归树25
2.3.3Master定理26
2.4习题27
第二部分朴素遍历
第3章线性表的遍历32
3.1基于遍历的选择与查找32
3.2基于遍历的排序33
3.2.1选择排序34
3.2.2插入排序35
3.3习题37
第4章图的深度优先遍历39
4.1图和图遍历39
4.2有向图的深度优先遍历40
4.2.1有向图的深度优先遍历框架40
4.2.2有向图的深度优先遍历树42
4.2.3活动区间43
4.3有向图的深度优先遍历应用45
4.3.1拓扑排序45
4.3.2关键路径48
4.3.3有向图中的强连通片50
4.4无向图的深度优先遍历54
4.4.1无向图的深度优先遍历树55
4.4.2无向图的深度优先遍历框架56
4.5无向图的深度优先遍历应用57
4.5.1容错连通57
4.5.2寻找割点58
4.5.3寻找桥60
4.6习题61
第5章图的广度优先遍历66
5.1广度优先遍历66
5.1.1广度优先遍历框架67
5.1.2有向图的广度优先遍历树70
5.1.3无向图的广度优先遍历树70
5.2广度优先遍历的应用72
5.2.1判断二分图72
5.2.2寻找k度子图73
5.3习题74
第三部分分治策略
第6章排序：从遍历到分治78
6.1快速排序78
6.1.1插入排序的不足78
6.1.2快速排序的改进79
6.1.3快速排序的分析81
6.2合并排序84
6.3基于比较的排序的下界86
6.3.1决策树的引入87
6.3.2比较排序最坏情况时间复杂度的下界88
6.3.3比较排序平均情况时间复杂度的下界88
6.4习题90
第7章堆的设计与应用95
7.1堆的定义95
7.2堆的抽象维护96
7.2.1堆的修复96
7.2.2堆的构建97
7.3堆的具体实现98
7.4堆的应用100
7.4.1堆排序100
7.4.2基于堆实现优先队列100
7.5习题101
第8章线性时间选择103
8.1期望线性时间的选择103
8.1.1期望线性时间的选择算法设计103
8.1.2期望线性时间的选择算法分析104
8.2最坏情况线性时间的选择106
8.2.1最坏情况线性时间的选择算法设计106
8.2.2最坏情况线性时间的选择算法分析107
8.3习题108
第9章对数时间查找110
9.1折半查找110
9.1.1经典折半查找110
9.1.2折半查找的推广111
9.2平衡二叉搜索树112
9.2.1二叉搜索树及其平衡性113
9.2.2红黑树的定义114
9.2.3红黑树的平衡性115
9.3习题116
第四部分贪心策略
第10章最小生成树120
10.1Prim算法120
10.1.1Prim算法的正确性122
10.1.2Prim算法的实现125
10.1.3Prim算法的分析126
10.2Kruskal算法127
10.2.1Kruskal算法的正确性128
10.2.2判断是否成环——基于并查集的实现129
10.2.3Kruskal算法的实现与分析133
10.3最小生成树贪心构建框架MCE134
10.3.1从MCE框架的角度分析Prim算法135
10.3.2从MCE框架的角度分析Kruskal算法136
10.4习题137
第11章给定源点的最短路径142
11.1Dijkstra算法142
11.1.1Dijkstra算法的设计142
11.1.2Dijkstra算法的正确性与性能分析144
11.2从Dijkstra算法到贪心遍历框架BestFS146
11.3习题147
第12章贪心策略的其他应用151
12.1相容任务调度问题151
12.1.1直觉的尝试151
12.1.2基于任务结束时间的贪心算法152
12.2Huffman编码153
12.2.1可变长度编码153
12.2.2最优编码方案的性质154
12.2.3贪心的Huffman编码156
12.3习题156
第五部分动态规划
第13章最短路径160
13.1有向无环图上的给定源点最短路径问题160
13.2传递闭包问题和Shortcut算法161
13.3所有点对最短路径：基于路径长度的递归163
13.4Floyd—Warshall算法：基于中继节点范围的递归164
13.5习题166
第14章动态规划算法168
14.1动态规划的动机168
14.2动态规划的基本过程169
14.2.1基于朴素遍历的递归170
14.2.2未作规划的递归171
14.2.3采用动态规划的递归171
14.3动态规划的应用174
14.3.1动态规划的要素174
14.3.2编辑距离问题175
14.3.3硬币兑换问题176
14.3.4最大和连续子序列问题178
14.3.5相容任务调度问题179
14.4习题179
第六部分计算复杂性理论初步
第15章多项式时间归约188
15.1问题间的归约188
15.1.1优化问题和判定问题188
15.1.2问题间归约的定义189
15.2多项式时间：解决问题与完成归约190
15.2.1多项式时间可解的问题190
15.2.2多项式时间归约191
15.3习题192
第16章NP完全问题的基本概念193
16.1NP完全问题的定义193
16.1.1NP问题的定义193
16.1.2NP难与NP完全问题的定义194
16.2NP完全性证明的初步知识195
16.2.1一般问题和特例问题195
16.2.2等价的问题196
16.3习题197
附录A数学归纳法199
附录B二叉树200
参考文献201

算法是计算的灵魂(spirit of computing)，而算法设计与分析的基础知识是计算机科学的基石。算法设计与分析的知识内容很丰富，可以从不同视角进行组织与阐述。一种视角是关注经典的算法问题，如排序、选择、查找、图遍历等；另一种视角是关注经典的算法设计策略，包括分治、贪心、动态规划等。本书的组织兼顾问题与策略两种视角。首先按照经典的算法设计策略，将书中的主体内容分为遍历、分治、贪心、动态规划4个部分。其次在每个部分之内，又围绕经典的算法问题来阐述该部分所着重讨论的策略。    本书集中讨论抽象的即与机器、实现语言无关的算法设计与分析。为此在主体内容之前，我们首先讲解计算模型的基础知识，它是后续抽象讨论算法设计与分析的基础。另外，在本书的最后，我们介绍计算复杂性的基础知识，试图让读者在了解了各类算法问题、学习了各种算法设计和分析技术之后，对算法问题的难度有一个总体性的认识。此外，一些对于算法设计与分析较为关键的数学知识将在附录中列出。本书的内容是作者在过去多年授课的过程中逐渐积淀而成的，所以它不是对算法设计与分析知识的一个百科全书式的覆盖，而是对一些重点内容的更专注的讨论。    本书内容和组织方式的设计针对一个学期的授课展开。在内容方面，本书可以分为前后两个部分。前一部分主要围绕元素的序关系展开，讨论排序、选择、查找这3个经典的算法问题。而这3个问题的求解同时又是分治策略的典型应用。后一部分主要围绕“图”这一数学结构展开，讲授图遍历、最小生成树、最短路径等经典图算法。同时，这些图算法背后的一个核心问题是图上特定结构——最小生成树、最短路径——的优化。围绕图优化，我们展示了贪心策略与动态规划策略的典型应用。    在授课形式方面，我们将课程分为主课与辅课这两种形式。主课主要围绕典型的算法问题、经典的算法展开。而辅课则围绕算法策略来展开，在讲述若干经典问题、经典算法之后，从策略的视角回顾最近阶段的经典算法，同时补充新的素材对相应的策略进行进一步的展示。除知识讲授之外，实践也是“算法设计与分析”课程的重要组成部分。算法设计与分析课程的实践分为两类：一类是传统的习题，即紧扣书本知识的习题，如一些简单定理的证明、紧扣算法细节的一些问题等；另一类是应用题，它需要读者对一个有一定现实意义的问题进行建模，并用书中的算法知识来求解。本书的应用题大都可以用于算法编程实现的训练。在实际授课中，我们挑选了部分应用题作为编程实现题，并基于开源的OnlineJudge平台进行自动评测，取得了良好的效果。    本书的素材主要源自于南京大学计算机系本科生“算法设计与分析”课程的授课内容。其中一部分素材来源于共同授课的其他老师，包括前期负责讲授主课并指导辅课教学的陈道蓄老师，以及后期共同分班讲授这门课程的钱柱中老师。还有一部分素材来自于经典的算法教科书和国外大学授课教师在其课程网站上发布的课程材料。另外，还要感谢“算法设计与分析”课程的两位助教魏恒峰和杨怡玲，他们对大量的课程资料进行了整理与提炼。最后要感谢上过这门课的学生，他们创造性的提问与解题时所犯的错误都为本书提供了宝贵的素材。    教学建议说明：南京大学计算机系“算法设计与分析”课程的讲授采用三种不同形式，即主课、辅课（tutorial）和习题课。    ●主课围绕各个主要知识点进行专题讲授。下面列出主课的授课计划，包括每次课的主题以及所对应的书本中的章节。    ●辅课的主要内容是对前一阶段主课知识的多角度解读，以及重点内容的强化。辅课的授课往往以围绕经典例题的讨论为主，以知识点的阐述为辅。    ●习题课的讲授主要包括书上习题的讲解，以及上机评测问题的讲解。习题课的讲授可以根据具体的教学、上机、考试等情况进行相应的安排。    教学章节教学要求课时主课一  准备知识（第1章）  计算模型的基础知识  抽象算法设计与分析的基本概念2主课二  数学基础（第2章）  函数渐近增长率的基本概念  简单蛮力算法的逐步改进2  递归方程的基本求解技术  基于Master定理的分治递归求解2辅课一  从算法设计与分析的角度重新审视数学的概念2主课三  排序（第3、6、7章）  线性表的遍历，从蛮力排序到快速排序2  堆结构的维护  堆结构的应用：堆排序与优先队列2  合并排序  基于比较的排序的下界2辅课二  排序：从简单遍历到分而治之2主课四  选择（第8章）  选择问题的简单特例  期望线性时间选择  最坏情况线性时间选择2主课五  查找（第9、10章）  折半查找  平衡二叉树的定义及平衡性分析2  动态等价关系下的查找  并查集的设计与分析2(续)教学章节教学要求课时辅课三  分治策略中的平衡性控制技术2主课六  图遍历（第4、5章）  DFS、BFS基本算法框架  DFS框架深入分析2  有向图中的DFS：拓扑排序、任务调度、强连通片识别2  无向图中的DFS：寻找割点、寻找桥2辅课四  BFS框架深入分析、图遍历的典型应用、DFS和BFS各自特色比较2主课七  图优化（第10~14章）  最小生成树：Prim算法、Kruskal算法2  最短路径：给定源点最短路径、所有点对间最短路径2  从图优化到一般优化问题求解：贪心策略、动态规划策略的典型应用4辅课五  图的贪心遍历框架、经典图优化问题的各种变体2主课八  计算复杂性理论初步（第15~16章）  P问题、NP问题基本概念  问题间归约基本概念2  NP完全问题基本概念  基本的NP完全性证明技术2辅课六  算法设计与分析——过去与未来：抽象算法设计与分析回顾、难问题求解技术简介（近似算法）、算法设计与分析前沿简介（随机算法、在线算法、并行分布式算法等）2