第 2 章 算法入门

- · -

在本章中，我们要向读者介绍一个贯穿本书的框架，后续的算法设计和分析都是在这个框架中进行的。这一部分内容基本上是完全独立的，也有对第 3 章和第 4 章中一些内容的引用。(本章还给出了几个求和的式子，具体如何求解这几个式子可以参见附录 A.)

首先，要分析一下如何用插入排序算法解决第 1 章中提出的排序问题。我们定义了一种“伪代码”，它对于编写过计算机程序的读者来说应该是熟悉的。我们要用这种伪代码来说明应该如何描述算法。在描述了算法之后，再证明它能正确地完成排序任务，并对其运行时间进行分析。在分析过程中，引入了一种记号，它侧重于表达算法的运行时间是如何随着待排序的数据项数而增加的。在讨论过插入排序算法后，还要介绍算法设计中的分治法( divide and conquer),并利用该方法来设计一个称为合并排序的算法。在本章的最后，对合并算法的运行时间进行了分析。