《算法设计与分析 第2版》黄宇 | PDF下载|ePub下载

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

算法是计算的灵魂（spirit of computing），而算法设计与分析的基础知识是计算机科学的基石。算法设计与分析的内容很丰富，可以从不同视角进行组织与阐述。一种视角是关注经典的算法问题，如排序、选择、查找、图遍历等；另一种视角是关注经典的算法设计策略，如分治、贪心、动态规划等。

根据这一“二维视角”，本书的核心内容分为四块，如图1 所示。从问题的视角看，主要有两类问题。第一类为序相关的问题，包括基于比较的排序、选择与查找；第二类为图相关的问题，包括基本的图遍历问题以及最小生成树、最短路径等图优化问题。从策略的视角看，主要有两类策略。第一类为遍历策略，包括线性表上的遍历和图上的遍历；第二类为优化策略，在序相关的问题上主要体现为分治策略，在图相关的问题上体现为贪心策略与动态规划策略。

图1 二维视角下的核心内容

上述核心内容是算法设计与分析中最基础的知识与最典型的技术。以此为基础，本书进一步讨论更深入的算法设计与分析技术。一类是围绕经典数据结构的算法设计与分析，另一类是进阶的算法分析策略。此外，本书集中讨论抽象的—— 与机器、实现语言无关的—— 算法设计与分析。为此，在主体内容之前，本书首先讲解计算模型的基础知识，它是后续抽象的算法设计与分析的基础。本书的最后介绍计算复杂性的基础知识，试图让读者在了解各类算法问题、学习各种算法设计与分析技术之后，对算法问题的难度有一个总体的认识。本书内容的总体结构如图2所示。

本书的内容是作者在多年授课的过程中逐渐积淀而成的，因而它不是对算法设计与分析知识的一个百科全书式的覆盖，而是对一些重点内容更专注的讨论。本书的内容和组织方式是面向一个学期的授课而设计的。在授课形式方面，我们将课程分为主课与辅课两种形式。主课主要围绕典型的问题、经典的算法展开，而辅课则主要围绕算法策略展开。若干次的主课讲授形成一个阶段，每一个阶段结束后，通过一次辅课从策略的视角回顾最近阶段的一组算法，同时补充新的素材对相应的策略进行进一步的讨论。

图2 本书内容总体结构

在知识讲授之外，实践也是算法设计与分析课程的重要组成部分。算法课程的实践分为两类。一类是传统的习题。本书习题大体按照这样的顺序给出：首先是紧扣书本知识的习题，例如一些简单定理的证明、紧扣算法细节的一些问题等；其次是应用题，它需要读者对一个具有一定现实意义的问题进行建模，并用书中的算法知识来解决问题。另一类是编程实现题。本书的应用题大都可以用于算法编程实现的训练。在实际授课中，我们挑选了部分应用题作为编程实现题，并基于开源的OnlineJudge 平台进行自动评测，取得了良好的效果。

本书的素材主要源自南京大学计算机系本科生“算法设计与分析”课程的授课内容。其中一部分素材来源于共同授课的其他老师，包括前期负责讲授主课并指导辅课教学的陈道蓄老师，以及后期共同分班讲授这门课程的钱柱中、张胜、徐经纬老师。还有一部分素材来源于经典的算法教科书和国外大学的授课教师在其课程网站上发布的课程材料。另外，还要感谢“算法设计与分析”课程早期的两位助教魏恒峰和杨怡玲，他们对大量的课程资料进行了整理与提炼。最后要感谢上过这门课的学生，他们创造性的提问与解题时所犯的错误为本书提供了宝贵的素材。