第一部分 基础知识

- · -

这一部分将引导读者开始思考算法的设计和分析问题，简单介绍算法的表达方法、将在本书中用到的一些设计策略，以及算法分析中用到的许多基本思想。本书后面的内容都是建立在这些基础知识之上的。

第 1 章是对算法及其在现代计算系统中地位的一个综述。本章给出了算法的定义和一-些算法的例子。它还说明了算法是一项技术，就像快速的硬件、图形用户界面、面向对象系统和网络一样。

在第 2 章中，我们给出了书中的第一批算法，它们解决的是对 n 个数进行排序的问题。这些算法是用一种伪代码形式给出的，这种伪代码尽管不能直接翻译为任何常规的程序设计语言，但足够清晰地表达了算法的结构，以便任何一位能力比较强的程序员都能用自己选择的某种语言将算法实现出来。我们分析的排序算法是插入排序，它采用了一种增量式的做法；另外还分析了合并排序算法，它采用了一种递归技术，称为“分治法”。尽管这两种算法所需的运行时间都随 n 的值而增长，但增长的速度是不同的。我们在第 2 章中分析了这两种算法的运行时间，并给出了一种有用的表示方法来表达这些运行时间。

第 3 章给出了这种表示法的准确定义，称为渐近表示。在第 3 章的一开始，首先定义了几种渐近记号，它们主要用于表示算法运行时间的上界和/或下界。第 3 章余下的部分主要给出了一些数学表示方法。这一部分的作用更多的是为了确保读者所用的记号能与本书中的记号体系相匹配，而不主要是教授新的数学概念。

第 4 章更深人地讨论了第 2 章引入的分治方法。特别地，第 4 章包含了解决递归式的方法。递归式主要用于描述递归算法的运行时间。“主方法”(master method)是一种功能很强的技术,它可以用于解决分治算法中出现的递归式。第 4 章中的相当一部分内容都是在证明主方法的正确性，如果跳过这一部分证明内容的话，也没有什么太大的影响。

第 5 章介绍了概率分析和随机化算法。概率分析一般用于确定一些算法的运行时间，在这些算法中，由于同一规模的不同输人可能有着内在的概率分布，因而在这些不同输人之下，算法的运行时间可能有所不同。在有些情况下，我们假定算法的输人符合某种已知的概率分布，于是，算法的运行时间就是在所有可能的输人之下，运行时间的平均值。在其他情况下，概率分布不是来自于输人，而是来自于算法执行过程中所做出的随机选择。如果一个算法的行为不仅由其输人决定，还要由一个随机数生成器所生成的值来决定的话，它就是一个随机化算法(randomized algorithm)。我们可以利用随机化算法，强行使算法的输人符合某种概率分布，从而确保不会有某一输人会始终导致算法的性能变坏；或者，对于那些允许产生不正确结果的算法，甚至能够将其错误率限制在某个范围之内。

附录 A~附录 C 包含了另一些数学知识，它们对读者阅读本书可能会有所帮助。在阅读本书之前，读者很可能已经知道了附录中给出的大部分知识(我们采用的某些符号约定与读者过去见过的可能会有所不同)，因而，可以将附录视为参考材料。另一方面，你很可能从未见过第一部分中给出的内容。第一部分中的所有各章和附录都是以一种人门指南的风格来编写的。