本书的内容围绕两条主线来组织。一条主线是介绍典范性的算法问题，如排序、选择、图遍历等。 另一条主线是介绍典范性的算法设计分析策略，如分治、贪心、动态规划等算法设计策略和对手分析、平摊分析等算法分析策略。本书中两条主线交替进行，每条主线又各自分为基本和进阶两部分。
本书源于作者“算法设计与分析”课程的10年教学实践，主要面向计算机专业本科生，以及其他需要学习计算机科学基本知识与了解计算机程序设计背后原理的读者。
本书的主要特色
内容定位科学。本书定位于讲解抽象的——与机器、实现语言无关的——算法设计与分析知识。这一定位有助于读者脱离具体的机器与编程语言的细节，了解算法设计背后的核心原理。
内容组织合理。本书内容组织兼顾问题和策略两个维度，围绕遍历、分治、贪心、动态规划这四种经典策略，通过排序、选择、查找、图遍历、图优化等经典算法问题的逐步深入求解，来展示各种算法设计策略的运用。本书内容具有“自包含（self-contained）”特色，读者只需具有离散数学的基础知识以及计算机程序设计的入门知识，即可进行学习。
习题资源丰富。本书为每章内容配备了丰富的习题。习题由浅入深，涵盖了主要知识点，其中部分习题改编自授课过程中学生常犯的典型错误示例。大部分习题不仅可以布置为书面习题，也易于配以输入输出数据，用作在线评测试题。
作者介绍
黄宇，南京大学计算机科学与技术系教授，博士生导师，主要研究方向为分布式算法、分布式系统和软件方法学。曾主持两项国家自然科学基金项目，并作为主要成员参与了国家973计划、国家自然科学基金创新群体项目等多项国家重大科研项目。2014年获得南京大学登峰人才支持计划资助，2011年获教育部技术发明奖。所指导的博士论文荣获2016年中国计算机学会优秀博士学位论文奖。已在IEEE Trans. on Computers、IEEE Trans. on Parallel and Distributed Systems、IEEE PerCom等重要国际期刊及会议上发表多篇论文。
算法是计算的灵魂(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
计算机\算法
本书源于作者“算法设计与分析”课程的10年教学实践，主要面向计算机专业本科生，以及其他需要学习计算机科学基本知识与了解计算机程序设计背后原理的读者。
本书的主要特色：
l）内容定位科学。本书定位于讲解抽象的——与机器、实现语言无关的——算法设计与分析知识。这一定位有助于读者脱离具体的机器与编程语言的细节，了解算法设计背后的核心原理。
2）内容组织合理。本书内容组织兼顾问题和策略两个维度，围绕遍历、分治、贪心、动态规划这四种经典策略，通过排序、选择、查找、图遍历、图优化等经典算法问题的逐步深入求解，来展示各种算法设计策略的运用。本书内容“自包含”，读者只需要具有离散数学的基础知识以及计算机程序设计的入门知识，即可学习本书内容。
3）习题资源丰富。本书为每章内容配备了丰富的习题。习题由浅入深，涵盖了主要知识点，其中部分习题改编自授课过程中学生常犯的典型错误。大部分习题不仅可以布置为书面习题，也易于配以输入输出数据，用作在线评测试题。
黄宇 编著：
黄宇，南京大学计算机科学与技术系教授，博士生导师，主要研究方向为分布式算法、分布式系统和软件方法学。曾主持两项国家自然科学基金项目，并作为主要成员参与了国家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模型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 对数log n17
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.3 Master定理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.1 Prim算法120
10.1.1 Prim算法的正确性122
10.1.2 Prim算法的实现125
10.1.3 Prim算法的分析126
10.2 Kruskal算法127
10.2.1 Kruskal算法的正确性128
10.2.2 判断是否成环——基于并查集的实现129
10.2.3 Kruskal算法的实现与分析133
10.3 最小生成树贪心构建框架MCE134
10.3.1 从MCE框架的角度分析Prim算法135
10.3.2 从MCE框架的角度分析Kruskal算法136
10.4 习题137
第11章 给定源点的最短路径142
11.1 Dijkstra算法142
11.1.1 Dijkstra算法的设计142
11.1.2 Dijkstra算法的正确性与性能分析144
11.2 从Dijkstra算法到贪心遍历框架BestFS146
11.3 习题147
第12章 贪心策略的其他应用151
12.1 相容任务调度问题151
12.1.1 直觉的尝试151
12.1.2 基于任务结束时间的贪心算法152
12.2 Huffman编码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.4 Floyd-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.1 NP完全问题的定义193
16.1.1 NP问题的定义193
16.1.2 NP难与NP完全问题的定义194
16.2 NP完全性证明的初步知识195
16.2.1 一般问题和特例问题195
16.2.2 等价的问题196
16.3 习题197
附录A 数学归纳法199
附录B 二叉树200
参考文献201
