前    言

　　计算机系统中的任何软件，都是按特定的算法来予以实现的。算法性能的好坏，直接决定了所实现软件性能的优劣。如何判定一个算法的性能？用什么方法来设计算法？所设计的算法需要多少运行时间、多少存储空间？在实现一个软件时，这些都是必须予以解决的问题。计算机中的操作系统、语言编译系统、数据库管理系统，以及各种各样的计算机应用系统中的软件，都离不开用具体的算法来实现。因此，算法设计与分析是计算机科学与技术的一个核心问题，也是大学计算机专业本科生及研究生必修的一门重要的专业基础课程。通过算法设计与分析这门课程的学习，读者能够掌握算法设计与分析的方法，并利用这些方法去解决在计算机科学与技术中所遇到的各种问题，设计计算机系统的各种软件中所可能遇到的算法，并对所设计的算法作出科学的评价。因此，算法设计与分析，不仅对计算机专业的科学技术人员，而且对使用计算机的其他专业技术人员，都是非常重要的。

　　本书的第2版对第1版进行了勘误和修订，充实了部分内容。本书内容选材适当，编排合理，由浅入深，循序渐进，互相衔接，逐步展开。在编写过程中，尽可能遵循下面几个原则。

　　（1）面对学生，尽可能用通俗的语言来表达深奥的问题。因此，公式推导尽可能详尽，因为这样才不会为难学生；所用到的专门术语或知识来龙去脉尽可能介绍清楚，因为这样，学生才不会感到错愕和不知所措；对问题的叙述，尽可能开门见山，使学生能较快地、容易地接触到问题的实质。

　　（2）实现算法的思想方法和推导过程尽可能详细和易于理解，因为这样，学生才能深刻地理解和掌握算法的工作原理。

　　（3）对算法的某些理论基础和定理的证明给以足够的重视，定义的叙述尽可能严谨，方法推导、定理证明的逻辑尽可能严密，因为这可以培养学生良好的逻辑思维能力和严谨规范的科学方法，而设计并实现一个算法，具有良好的逻辑思维能力和严谨规范的科学方法是很重要的。

　　（4）算法具体实现的描述、所涉及到的数据结构和变量，都作出较为详尽的说明。因为有些学生尽管知道了思想方法，也了解了实现步骤，但具体实现起来，有时却觉得束手无策。对算法的具体实现和所用到的数据结构的较为详细的描述，可以培养学生的具体实践能力，使学生学会如何使用所学过的知识来设计和实现某些算法。

　　（5）算法的工作过程，尽可能详细说明。对工作过程中比较难于理解的某些算法，则通过实例，从头到尾地模拟算法的运行。因为这是学习、理解算法的关键，没有用实例来模拟算法的运行，学生学完了以后，对该算法也只能是懵懂的，不知其所以然。

　　（6）无论是算法的基本概念、算法复杂性的分析方法，还是算法的实现步骤，都尽可能提供大量实例加以解释说明。

　　本书先以最简单的穷举法为例，说明算法设计技术及算法分析的重要性；接着以排序问题中的一些基本算法和其他一些算法为例，说明算法复杂性的一般分析方法；然后以算法设计技术为纲，按照实现算法的思想方法、实现步骤、所涉及到的数据结构、算法的具体描述及复杂性分析等几个方面，逐个介绍各种算法设计技术及其分析方法。

　　全书分为4部分。第1部分包括第1章和第2章，介绍算法设计与分析的基本概念。第1章介绍算法的定义及算法的时间复杂性的基本概念；第2章介绍算法时间复杂性的分析方法，并简单介绍与算法分析有关的最基本的数学工具。第2部分包括第3~9章，介绍算法设计的基本技术。第3章继续介绍排序问题和离散集合的操作，进一步对算法分析进行了阐述，并为下面各章中所涉及到的问题作了技术上的准备；第4章介绍递归技术及分治方法，从理论上分析了分治算法的效率；第5章介绍贪婪法的设计方法及其正确性的证明；第6章介绍动态规划法的设计技术；第7章介绍回溯法的设计技术；第8章在回溯法的基础上，介绍分支与限界方法的应用及其分析；第9章介绍3种类型的随机算法及其性能分析。第3部分包括第10~11章，涉及计算机应用领域里的一些算法。第10章介绍图和网络流的一些问题；第11章介绍计算几何中的一些问题。第4部分包括第12~15章，介绍算法设计与分析中的一些理论问题。第12章介绍NP完全问题；第13章介绍计算复杂性问题；第14章介绍下界理论问题；第15章介绍近似算法及其性能分析。

　　许存权编辑为本书的出版付出了大量的工作和努力，在此表示诚挚的谢意。

　　由于水平有限，书中难免存在不当之处，敬请读者指正。

　　编  者

算法设计与分析（第2版）

III

前    言

·II·