前言

本书为普通高等教育“十一五”国家级规划教材。

算法设计与分析不仅是计算机科学与技术专业学生的必备知识，也是计算机应用工作者必不可少的基础知识。掌握扎实的算法设计与分析理论和方法有助于理工科学生进一步学习计算机技术，适应更广泛的职业挑战。

计算机学科教学计划2001（Computing Curricula 2001，简称CC2001）将计算机学科分成14个领域，每个领域分成若干个知识单元，每个知识单元又包括若干个主题。CC2001强调算法，重视算法设计与分析能力和程序设计能力。计算机算法的基本内容主要包含在算法与复杂性（Algorithm And Complexity，简称AL）和程序设计基础（Programming Fundamental，简称PL）等知识领域中。在CC2001建议的计算机科学与技术专业的280个核心学时中，程序设计与算法方面分配90个核心学时，约占总核心学时的32.1%。

算法领域涉及的内容广泛，通常包括迄今为止，算法学家们所设计的许多基本和经典算法，如排序、搜索、图算法、组合问题算法、字符串算法和大量的数值算法，算法问题求解、算法分析技术和常用的算法设计策略，可计算性理论和问题复杂性的研究，如计算模型、NP完全问题和问题复杂度下界理论。近年来，算法研究在随机算法、近似算法、密码算法、分布式算法和并行算法，以及其他算法方面也都有很多新成果。

作为“算法设计与分析”课程教材，根据我国在算法与数据结构方面课程开设的实际情况，本书不再重复属于我国传统“数据结构”课程中的基本数据结构和算法的内容，但选用快速排序等在“数据结构”课程中已学过的若干排序、搜索和图算法，它们被作为算法设计策略和算法分析的实例使用。这种做法不是内容的简单重复，而是必要的和有益的深化。以学生熟知的知识为基础，介绍新知识，可使学生更容易理解和接受新的算法知识。

算法知识理论性较强，涉及的范围又很广，给学习和理解造成困难。为了将本书写成条理清晰、内容翔实、逻辑严谨、深入浅出的“算法设计与分析”教材，作者做了以下努力。

首先，本书分3部分组织内容，力求做到结构清晰、内容取舍恰当。

其次，书中算法都有完整的C++程序，程序结构清楚，构思精巧，对程序代码都做了详细注释，所有程序都已在VC++环境下编译通过并能正确运行，它们既是学习算法设计的示例，也是很好的C++程序设计示例。

此外，本书通过大量实例和图示介绍算法，并有丰富的习题，便于自学。

这样做的目的是在保持算法科学性的同时，加强其技术性和实用性，也降低算法学习的难度，使复杂抽象的算法设计更容易为学习者理解和掌握。这也体现了计算机学科的科学性和工程性、理论性和实践性并重的学科特点。

全书包括3部分：算法和算法分析、算法设计策略及求解困难问题。

第1部分介绍算法概念、算法问题分类和问题求解方法，算法复杂度、递归技术，还介绍了两种新的数据结构：跳表和伸展树，以及它们特定的算法分析方法。

第2部分讨论常用的算法设计策略：基本搜索和遍历方法、分治法、贪心法、动态规划法、回溯法和分枝限界法。对于每种算法设计策略，通常先介绍一般方法，然后使用该策略解决若干经典的算法问题。

第3部分介绍NP完全问题、随机算法、近似算法，并对现代密码学和数论算法也做了简要论述。

本书作者在南京邮电大学讲授“算法设计与分析”和“数据结构”课程多年。本书是在作者编写出版的多本关于算法与数据结构领域教材的基础上，参考了近年来国内外多种算法设计与分析的优秀教材编写而成的。本书的编写得到了电子工业出版社的大力支持，并得到了南京邮电大学和计算机学院领导的推荐和关心，在此表示衷心感谢。

书中若有不妥之处，敬请读者批评指正。

作者