分析框架

本节中，概要地描述一个分析算法效率的一般性框架。必须指出，有两种算法效率：时间效率和空间效率。对于大多数问题来说，在速度上能够取得的进展要远远大于空间上的进展。所以，我们把主要精力集中在时间效率上，这里的分析框架对于分析空间效率也是适用的。

输入规模的度量

首先考虑输入规模的度量单位，一个显而易见的事实：算法对于规模更大的输入需要运行更长的时间。所以，使用一个以算法输入规模n为参数的函数，来研究算法效率是非常合乎逻辑的。例如，对于排序，查找，寻找列表的最小元素以及其他大多数和列表打交道的问题，这个参数就是列表的长度。n次多项式P(x) = anxn + … + a0求值的问题，参数是多项次的次数，或者是它系数的个数，系数的个数比次数大一。这样一个细小的差别对于效率分析来说是无关紧要的。

有些情况下，选择哪个参数表示输入规模是有差别的，这受到所讨论算法的操作细节的影响。我们注意选择谁人规模的合适量度。例如，对于一个拼写检查算法，如果算法对于输入的每一个独立字符都要做检查，我们使用字符的数量来度量输入规模；如果它的操作是以单词为单位，我们应该统计输入中词的数量。

运行时间的度量单位

接下来考虑算法运行时间的度量单位。我们不使用秒，毫秒之类的时间度量，因为它依赖于计算机硬件，编译器，同时时间运行时间计时也很困难。

我们统计算法基本操作的执行次数，即算法中最重要的操作。它们对总运行时间的贡献最大。

一个算法的基本操作：它通常是算法最内层循环中最费时的操作。例如，排序算法是通过比较列表总的待排序元素(键)工作的，故其基本操作就是对键的比较。

这就是一个算法时间效率的分析框架。对于输入规模为n的算法，可以统计它的基本操作执行次数，来对其效率进行度量。2.3节和2.4节分别介绍计算非递归算法和递归算法的“执行次数”。

该框架的一个重要应用。约定，Cop为一个算法基本操作的执行时间，而C(n)是该算法需要执行基本操作的次数。然后，对运行在那台计算机上的某个算法程序的运行时间，用以下公式做估计：

这个公式可以回答这种问题：“如果这个算法运行在一台比我们现在的机器快十倍的机器上，它运行地有多快呢？很明显答案是10倍。

或者假设C(n) = 1/2n(n-1),如果输入规模翻倍，该算法会运行多长时间呢？

答案是大约要运行4倍的时间。

注意，我们不需要知道Cop的值就能够回答刚才的问题：这个值在做出发的时候已经完全被约去了。还需要注意的是，C(n)公式的乘法常量1/2也被越饿去了。因此，对于大规模的输入，我们的效率分析框架忽略执行次数C(n)中的乘法常量，而仅关注执行次数的增长次数及其常熟倍。

增长次数

对于大规模的输入要强调执行次数的增长次数。

表2.1中数字的数量级对于算法的分析具有深远意义。这些函数中增长最慢的是对数函数，其次是线性函数，然后是线性的对数函数。

如果一个程序具有对数级的基本操作次数，该程序对于任何实际规模的输入都会在几乎瞬间内完成。虽然特定的操作次数明显依赖于对数的底，通过以下方程：

允许对数在不同的底之间转换，并且仅在对数部分以外新增一个乘法常量。这就是为什么当我们仅对函数的增长次数及其常数倍感兴趣时，我们甚至可以忽略对数的底，简单地写成logn.

幂函数2^n和阶乘函数n!.常常倾向于把两者都作为“呈指数级增长的函数”（或者简称为“指数级”），尽管严格来讲，只有前者才能这么称呼。一个需要记住的要点是：

一个需要指数级操作次数的算法只能用来解决规模非常小的问题。

算法的最优，最差和平均效率

以算法输入规模为参数的函数可以合理地度量算法的效率。但许多算法的运行时间不仅取决于输入的规模，而且取决于特定输入的细节。例如，顺序查找。在n个元素的列表中查找一个给定的项(某些查找键),它会检查列表中的连续元素，直到发现了匹配查找键的元素或者达到了列表的终点。下面是该算法的伪代码，为简单起见，其中的列表是用数组来实现的(同时假设，如果数组下标i是否越过上界n为假，则不会判断第二个条件A[i] ≠ K).

算法 SequentialSearch(A[0..n-1], K)
    //用顺序查找在给定的数组中查找给定的值
    //输入：数组A[0..n-1]和查找键K
    //输出：返回第一个匹配K的元素的下标
    //      如果没有匹配元素，则返回-1
    i <- 0
    while i < n and A[i] ≠ K do
        i <- i + 1
    if i < n return i
    else return -1

很明显，对于规模同样为n的列表来说，算法的运行时间会有很大的差异。最坏的额情况下，表中会没有匹配元素或者第一个匹配元素恰巧是列表的尾元素，这个算法的键值比较次数达到最大：Cworst(n) = n.

算法的最差效率指当输入规模为n时，算法在最坏情况下的效率。相对其他的输入，该算法的运行时间最长。确定算法最差效率的方法是：先对算法作一个分析，规模为n的所有可能输入中，哪种类型的输入会导致基本操作次数C(n)达到最大值，然后再计算这个“最差值”Cworst(n).通过确定算法运行时间的上界，分析最坏的情况，保证算法的运行时间不会超过最坏输入情况下的运行时间——Cworst(n).

算法的最优效率指当输入规模为n时，算法在最优情况下的效率。与其他输入相比，该算法运行得最快。我们可以这样来分析最优效率：首先确定，所有规模n得可能输入中，哪种谁人类型对应最小得C(n)值(注意，最优情况并不是指规模最小的输入；而是使算法运行得最快的，规模为n的输入）。然后确定，在最理想的输入条件下的运行时间Cbest(n).

对于接近于最优输入的有用输入类型，选择能达到其最有效率的算法对其进行处理。例如，插入排序，最优输入是已经排过序的数组，因此选择这种算法对基本有序的数组进行操作。

平均效率提供给我们信息：在“典型”或者“随机”输入的情况下，一个算法会具有什么眼的行为.为分析算法的平均效率，必须对规模为n的可能输入做一些假设。

我们考虑以下顺序查找。标准的假设是: (a)成功查找的概率是P(0 ≦ P ≦ 1);第一次匹配发生在列表第i个位置的概率是相同的。基于这两个假设，求出键值比较的平均次数Cavg(n).在成功查找的情况，第一次匹配发生在列表的第i个位置的可能性是P/n,比较次数是i。在不成功查找的情况下，比较的次数是n，而这种情况发生的可能性是(1-P).

Cavg(n) = [1·P/n + 2·P/n + ... + i·P/n + ... + n·P/n] + n·(1-P)
        = P/n[1 + 2 + ... + i + ...n] + n(1-P)
        = P/n·n(n+1)/2 + n(1-P)
        = P(n+1)/2 + n(1-P)

从这个一般性的方程推出一些非常合理的结论。例如，如果P=1(查找一定会成功),顺序查找所做的键值比较的平均次数是(n+1)/2; 这意味着，平均来说，该算法大约要检查表中一半的元素。如果P=0(查找一定不会成功),键值比较的平均次数将是n，对于这种输入，该算法会对n个元素全部检查一遍。

研究平均效率的直接方法包括将规模为n的实例划分为几种类型，算法基本操作执行的次数都是相同的类型。然后通过得到各类输入的概率分布，推倒基本操作的平均次数。

我们真的需要直到算法的平均效率。有许多重要的算法的平均效率比它们对于悲观的最差效率要好得多。分析平均效率，以致于不会错失许多重要的算法。

还有一种类型的效率称为摊销效率.它不适用于算法的单次运行，而是应用于算法对于同样数据结构所执行的一系列操作。有些情况下，单次运行的时间代价是比较高昂的，但n次运行的总运行时间总是明显优于单次执行的最差效率乘以n。我们能把这样一次最差效率的高成本摊销到整个序列总去。在9.2节讨论求不相交集合并集的算法时，会看到关于摊销效率的价值的一个例子。