内容简介
本书讲授算法设计与分析的基础知识。首先介绍计算模型的基本概念；其次围绕遍历、分治、贪心、动态规划这四个经典算法设计策略，讲解了排序、选择、查找、图遍历、小生成树、短路径等经典算法问题；后介绍了计算复杂性的基础知识。本书主要面向计算机专业本科生，以及其他需要学习计算机科学基础知识与了解计算机程序设计背后原理的读者。
目录
前言
教学建议
第一部分 计算模型
第1章 抽象的算法设计与分析
1.1 RAM模型的引入
1.2 抽象算法设计
1.3 抽象算法分析
1.4 习题
第2章 从算法的视角重新审视数学的概念
2.1 数学运算背后的算法操作
2.2 函数的渐近增长率
2.3 “分治递归”求解
2.4 习题
第二部分 朴素遍历
第3章 线性表的遍历
3.1 基于遍历的选择与查找
3.2 基于遍历的排序
3.3 习题
第4章 图的深度优先遍历
4.1 图和图遍历
4.2 有向图的深度优先遍历
4.3 有向图的深度优先遍历应用
4.4 无向图的深度优先遍历
4.5 无向图的深度优先遍历应用
4.6 习题
第5章 图的广度优先遍历
5.1 广度优先遍历
5.2 广度优先遍历的应用
5.3 习题
第三部分 分治策略
第6章 排序：从遍历到分治
6.1 快速排序
6.2 合并排序
6.3 基于比较的排序的下界
6.4 习题
第7章 堆的设计与应用
7.1 堆的定义
7.2 堆的抽象维护
7.3 堆的具体实现
7.4 堆的应用
7.5 习题
第8章 线性时间选择
8.1 期望线性时间的选择
8.2 最坏情况线性时间的选择
8.3 习题
第9章 对数时间查找
9.1 折半查找
9.2 平衡二叉搜索树
9.3 习题
第四部分 贪心策略
第10章 最小生成树
10.1 Prim算法
10.2 Kruskal算法
10.3 最小生成树贪心构建框架MCE
10.4 习题
第11章 给定源点的最短路径
11.1 Dijkstra算法
11.2 从Dijkstra算法到贪心遍历框架BestFS
11.3 习题
第12章 贪心策略的其他应用
12.1 相容任务调度问题
12.2 Huffman编码
12.3 习题
第五部分 动态规划
第13章 最短路径
13.1 有向无环图上的给定源点最短路径问题
13.2 传递闭包问题和Shortcut算法
13.3 所有点对最短路径：基于路径长度的递归
13.4 Floyd-Warshall算法：基于中继节点范围的递归
13.5 习题
第14章 动态规划算法
14.1 动态规划的动机
14.2 动态规划的基本过程
14.3 动态规划的应用
14.4 习题
第六部分 计算复杂性理论初步
第15章 多项式时间归约
15.1 问题间的归约
15.2 多项式时间：解决问题与完成归约
15.3 习题
第16章 NP完全问题的基本概念
16.1 NP完全问题的定义
16.2 NP完全性证明的初步知识
16.3 习题
附录A 数学归纳法
附录B 二叉树
参考文献
前言
算法是计算的灵魂(spirit of computing)，而算法设计与分析的基础知识是计算机科学的基石。算法设计与分析的知识内容很丰富，可以从不同视角进行组织与阐述。一种视角是关注经典的算法问题，如排序、选择、查找、图遍历等；另一种视角是关注经典的算法设计策略，包括分治、贪心、动态规划等。本书的组织兼顾问题与策略两种视角。首先按照经典的算法设计策略，将书中的主体内容分为遍历、分治、贪心、动态规划4个部分。其次在每个部分之内，又围绕经典的算法问题来阐述该部分所着重讨论的策略。
本书集中讨论抽象的即与机器、实现语言无关的算法设计与分析。为此在主体内容之前，我们首先讲解计算模型的基础知识，它是后续抽象讨论算法设计与分析的基础。另外，在本书的最后，我们介绍计算复杂性的基础知识，试图让读者在了解了各类算法问题、学习了各种算法设计和分析技术之后，对算法问题的难度有一个总体性的认识。此外，一些对于算法设计与分析较为关键的数学知识将在附录中列出。本书的内容是作者在过去多年授课的过程中逐渐积淀而成的，所以它不是对算法设计与分析知识的一个百科全书式的覆盖，而是对一些重点内容的更专注的讨论。
本书内容和组织方式的设计针对一个学期的授课展开。在内容方面，本书可以分为前后两个部分。前一部分主要围绕元素的序关系展开，讨论排序、选择、查找这3个经典的算法问题。而这3个问题的求解同时又是分治策略的典型应用。后一部分主要围绕“图”这一数学结构展开，讲授图遍历、最小生成树、最短路径等经典图算法。同时，这些图算法背后的一个核心问题是图上特定结构——最小生成树、最短路径——的优化。围绕图优化，我们展示了贪心策略与动态规划策略的典型应用。
在授课形式方面，我们将课程分为主课与辅课这两种形式。主课主要围绕典型的算法问题、经典的算法展开。而辅课则围绕算法策略来展开，在讲述若干经典问题、经典算法之后，从策略的视角回顾最近阶段的经典算法，同时补充新的素材对相应的策略进行进一步的展示。除知识讲授之外，实践也是“算法设计与分析”课程的重要组成部分。算法设计与分析课程的实践分为两类：一类是传统的习题，即紧扣书本知识的习题，如一些简单定理的证明、紧扣算法细节的一些问题等；另一类是应用题，它需要读者对一个有一定现实意义的问题进行建模，并用书中的算法知识来求解。本书的应用题大都可以用于算法编程实现的训练。在实际授课中，我们挑选了部分应用题作为编程实现题，并基于开源的OnlineJudge平台进行自动评测，取得了良好的效果。
本书的素材主要源自于南京大学计算机系本科生“算法设计与分析”课程的授课内容。其中一部分素材来源于共同授课的其他老师，包括前期负责讲授主课并指导辅课教学的陈道蓄老师，以及后期共同分班讲授这门课程的钱柱中老师。还有一部分素材来自于经典的算法教科书和国外大学授课教师在其课程网站上发布的课程材料。另外，还要感谢“算法设计与分析”课程的两位助教魏恒峰和杨怡玲，他们对大量的课程资料进行了整理与提炼。最后要感谢上过这门课的学生，他们创造性的提问与解题时所犯的错误都为本书提供了宝贵的素材。
