第2章　算法基础

本章将要介绍一个贯穿本书的框架，后续的算法设计与分析都是在这个框架中进行的。这一部分内容基本上是独立的，但也有对第3章和第4章中一些内容的引用（本章也包含几个求和的式子，附录A将给出如何求和）。

首先，我们考察求解第1章中引入的排序问题的插入排序算法。我们定义一种对于已经编写过计算机程序的读者来说应该熟悉的“伪代码”，并用它来表明我们将如何说明算法。然后，在说明了插入排序算法后，我们将证明该算法能正确地排序并分析其运行时间。这种分析引入了一种记号，该记号关注时间如何随着将被排序的项数而增加。在讨论完插入排序之后，我们引入用于算法设计的分治法并使用这种方法开发一个称为归并排序的算法。最后，我们分析归并排序的运行时间。