算法导论——第2章

算法导论——第2章 算法基础

简介

本章将要介绍一个贯穿本书的框架，后续的算法设计与分析都是在这个框架中进行的。

这一部分内容基本上是独立的，但也有对第3章和第4章中一些内容的引用（本章也包含几个求和的式子，附录A将给出如何求和）。

首先，我们考察求解第1章中引入的排序问题的插入排序算法。我们定义一种对于已经编写过计算机程序的读者来说应该熟悉的“伪代码”，并用它来表明我们将如何说明算法。

然后，在说明了插入排序算法后，我们将证明该算法能正确地排序并分析其运行时间。这种分析引入了一种记号，该记号关注时间如何随着将被排序的项数而增加。

在讨论完插入排序之后，我们引入用于算法设计的分治法并使用这种方法开发一个称为归并排序的算法。

最后，我们分析归并排序的运行时间。

2.1 插入排序

排序问题的问题陈述：

输入：n个数的一个序列

输出：输入序列的一个递增排序

插入排序类似于排序手中的扑克牌，对于少量元素，它是一个有效的算法。

//insertion-sort(A):
for j=2 to A.length
    key = A[j]
    //insert a[j] into the sorted sequence A[1..j-1]
    i = j - 1
    while i>0 and A[i]>key
        A[i+1] = A[i]
        i = i-1
    A[i+1] = key

插入排序的循环不变式为A[1..j-1]。循环不变式主要用来帮助我们理解算法的正确性。需要满足三条性质：

1. 初始化：循环的第一次迭代前，它为真
2. 保持：如果在循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
3. 终止：在循环终止时，不变式为我们提供一个有用的性质，该性质帮助证明算法是正确的。

伪代码中的一些约定：

1. //表示该行后面部分是注释。
2. for X to / downto Y by M表示将X每次递增（to）M或者递减（downto）M到Y
3. 缩进表示块结构
4. 变量若不显式说明，一般为局部变量
5. A[i]表示A数组的第i个元素

2.2 分析算法

分析算法的结果意味着需要预测算法所需要的资源。

插入排序算法的分析。我们通常把一个程序的运行时间描述成其输入规模的函数。为此我们需要定义运行时间和输入规模。

输入规模的最佳概念依赖于研究的问题。对于研究的每个问题，我们将指出所使用的输入规模量度。

一个算法的在特定输入上的运行时间是指执行的基本操作数或步数。

分析插入排序算法的过程：

1. 首先给出伪代码中，每条语句的执行时间和执行次数。
   
2. 将代价与次数列对应元素之积求和，求得该算法的运行时间
   
3. 最佳情况（也就是全都排列好了）的运行时间，可以表示为
   $$
   an+b
   $$
   它是n的*线性函数。
   
4. 最差情况（也就是数组反向排序）的运行时间，可以表示为
   $$
   an^2 + bn + c
   $$
   它是n的二次函数。

一般情况下，我们习惯于研究最差情况。在某些特殊的情况下，我们会对一个算法的平均情况运行时间感兴趣。

我们真正感兴趣的是运算时间的增长率和增长量级。所以我们只考虑公式中最重要的项，就是高阶项，而忽略低阶项和常数项。

2.3 设计算法

本节我们考查另一种称为“分治法”的设计方法。第4章将更深入地探究该方法。

我们将用分治法来设计一个排序算法，该算法的最坏情况运行时间比插入排序要少得多。

分治算法的优点之一是，通过使用第4章介绍的技术往往很容易确定其运行时间。

2.3.1 分治法

分治法的思想：将原问题分解成几个规模较小但类似于原问题的子问题。递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

归并排序算法完全遵循分治模式。直观上其操作如下:

1. 分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。
2. 解决：使用归并排序递归地排序两个子序列。
3. 合并：合并两个已排序的子序列以产生已排序的答案。

调用Merge(A,p,q,r)将已排序数组A[p..q]和A[q+1..r]合并，伪代码如下：

//Merge(A, p, q, r)
n1 = q - p + 1;
n2 = r - q;
Let L[1..n1+1] and R[1..n2+1] be new arrays
for i=1 to n1
    L[i] = A[p+i-1];
for j=1 to n2
    R[j] = A[q+j];
L[n1+1] = \infity;
R[n2+1] = \infity;
i=1;
j=1;
for k=p to r
    if L[i] <= R[j]
        A[k] = L[i]
        i = i+1
    else
        A[k] = R[j]
        j = j+1

循环不变式为A[p,k-1]，为了证明算法正确性，它需要满足：

1. 初始化：迭代前k=p时，A[p..k-1]为空。它为真
2. 保持：因为L和R数组都是已经排序好的数组，所以每次选出来的确实是最小值。如果L[i]<=R[j]，将L[i]复制给A[k]，增加i和k的值后，为下次迭代建立了该循环不变式，反之亦然。
3. 终止：终止时k=r+1，A[p..k-1]就是A[p..r]且按照从小到大的顺序包含L和R数组除了哨兵之外的所有元素。

Merge的运行时间是：
$$
\theta(n)
$$
所以归并排序算法的伪代码如下：

//merge-sort(A, p, r)
if p<r
    q= (p+r)/2
    merge-sort(A, p, q)
    merge-sort(A, q+1, r)
    merge(A, p, q, r)

2.3.2 分析分治算法

当一个算法包含对其自身的递归调用时，我们往往可以用递归方程或递归式来描述其运行时间。

该方程根据在较小输入上的运行时间来描述在规模为n的问题上的总运行时间。

然后我们可以使用数学工具来求解该递归式并给出算法性能的界。

分治算法运行时间的递归式来自基本模式的三个步骤，假设T(n)是规模为n的一个问题的运行时间：

1. 分解。将原问题分解成a个子问题，每个子问题的规模是原问题的1/b，a不一定等于b。分解问题**所需的时间为D(n)**。
2. 解决。对于一个规模为n/b的子问题，需要T(n/b)的运行时间，所以需要aT(n/b)的时间来求解a个子问题。
3. 合并。将子问题的解合并成原问题的解需要**时间C(n)**。

若问题规模n小于等于某个常量c时，可以直接求得运行时间，那么得到递归式：
$$
T(n)=
\begin{cases}
\theta(1)，& \text{若 }n \leq c \
aT(n/b) + D(n) + C(n)，& \text{其他 }
\end{cases}
$$
为了对归并排序算法进行分析，我们建立归并排序n个数的最坏情况运行时间T(n)的递归式：