本书系统地介绍算法设计与分析的概念和方法，共四部分内容，第一部分包括前两章，介绍算法设计与分析的基本概念及必要的数学工具，对算法的时间复杂性的概念及算法的分析方法作了较为详细的叙述。第二部分包括第3—9章，以算法设计技术为纲，从排序问题和离散集合的操作开始，进而介绍递归技术、分治法、贪婪法、动态规划、回溯法、分支与限界法以及随机算法等算法设计技术及其复杂性。第三部分包括第10章和第11章，介绍计算机应用领域里的一些算法，第四部分包括第12-15章，介绍算法设计与分析中的一些理论问题，最后介绍了近似算法及其性能分析。

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

本书的内容选材适当，循序渐进，互相衔接，逐步展开。先以最简单的穷举法为例，说明算法设计技术及算法分析的重要性；接着以排序问题中的某些算法为例，说明算法分析的一般方法；然后以算法设计技术为纲，按照所叙述算法的思想方法、实现步骤、所涉及到的数据结构、算法的具体描述以及复杂性分析等几个方面，逐个介绍各种算法设计技术及其分析方法。

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

本书是在许存权编辑的大力支持和努力下才得以出版的；王淑娟同志为本书做了大量的工作，在此一并表示诚挚的谢意。

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

编者

2004年11月