第2章 算法分析基础

一旦确信一个算法是正确的，下一个重要的步骤就是分析算法。算法分析是指对算法利用时间和空间这两种资源的效率进行研究。本章讨论衡量算法效率的时间复杂度和空间复杂度，算法的最好、平均和最坏情况时间复杂度，讨论用于算法分析的渐近表示法，介绍如何使用递推关系来分析递归算法的方法及分摊分析技术。

2.1 算法复杂度

同一个问题可以编写多个算法来求解，这些算法所消耗的计算机资源（计算时间和存储空间）多少不同。算法的复杂度是指运行一个算法所需的时间和空间资源的量。

2.1.1 什么是好的算法

人们总是希望算法具有许多良好的特性。一个好的算法应具有以下4个重要特性。

（1）正确性（correctness）：毫无疑问，算法的执行结果应当满足预先规定的功能和性能要求。

（2）简明性（simplicity）：算法应思路清晰、层次分明、容易理解、利于编码和调试。

（3）效率（efficiency）：算法应有效使用存储空间，并具有高的时间效率。

（4）最优性（optimality）：算法的执行时间已达到求解该类问题所需时间的下界。

算法的正确性是指在合法的输入下，算法应实现预先规定的功能和计算精度要求。与算法正确性直接相关的是程序的正确性。对于大型程序，人们无法奢望它“完全正确”，而且这一点也往往无法证实，这就引出对程序健壮性（robustness）的要求。程序健壮性是指当输入不合法数据时，程序应能做适当处理而不至于引起严重后果。一个程序也许不能做到完全正确，但可以要求它是健壮的。其含义是：当程序万一遇到意外时，能按某种预定方式做出适当处理。正确性和健壮性是相互补充的。正确的程序并不一定是健壮的，而健壮的程序并不一定绝对正确。一个可靠的程序应当能在正常情况下正确地工作，而在异常情况下，亦能做出适当处理，这就是程序的可靠性（reliability）。

注意，本书假定算法的输入都是合法输入，而不进行输入检测，但在算法的实际应用中，应当对输入数据实施必要的检测来保证程序的健壮性。

算法的简明性要求算法的逻辑清晰，简单明了，并且是结构化的，从而使算法易于阅读和理解，并易于编码和调试。算法的简明性没有严格定义的尺度可以度量，在很大程度上取决于审视者的眼光。但简明性并不是可有可无的特性，它是算法设计者需努力争取的一个重要特性，因为简单的算法往往更容易理解和实现，相应的程序也会因此而减少错误（bug）。此外，一个简单明了的算法就像一篇优美的说明文，令阅读者赏心悦目。但遗憾的是，简单的算法并不一定是高效的。

算法的效率是指执行一个算法所需的计算时间和存储空间。当程序规模较大时，算法的效率问题是算法设计必须面对的一个关键问题。必须重视算法的效率分析。然而为了换取一定的效率，牺牲算法的可读性，在现代程序设计中并不是明智之举。因此，算法设计者往往需要在算法的简明性和效率之间做出谨慎的选择。折中和结论（tradeoffs and consequences）是计算机学科的重要概念之一。

算法的最优性与所求解的问题自身的复杂程度有关。例如，对于在n个元素的集合中寻找一个最大元素的问题，分析表明，任何通过元素之间比较的方式来求解此问题的正确算法，至少需要进行n-1次元素间的比较运算。如果某人编写一个算法，声称他的算法对任意一个有n个元素的集合，仅需执行n-2次元素比较便可求得集合中的最大元素，那么，可以肯定，该算法不可能是正确的。如果一个实际的正确算法，在最坏情况下的确只需n-1次元素比较便可求得最大元素，那么它可称为最优的。因为n-1次元素比较是求最大元问题所需时间的下界。本书将讨论排序和查找问题的时间下界。然而遗憾的是，许多看似简单的问题，至今仍无法知晓求解该问题所需的时间下界是多少，如：矩阵乘法。

2.1.2 影响程序运行时间的因素

一个程序的运行时间是程序运行从开始到结束所需的时间。影响程序运行时间的因素主要有：

（1）程序所依赖的算法；

（2）问题规模和输入数据；

（3）计算机系统性能。

首先，很容易想到，对于同一程序和相同的输入数据，如果在不同的计算机上运行该程序，所需的运行时间几乎可以肯定是不同的。这是因为计算机的硬件性能可能不同，特别是处理器（CPU）速度可能相差很多。程序设计语言及其编译器不同，生成的目标代码的效率也会各异。操作系统也是影响计算机系统性能的因素之一。这就是说，算法运行所需的时间依赖于计算机软、硬件系统。

如果排除计算机的因素，假定在完全相同的计算机环境下运行程序，情况又如何呢？

很显然，求解同一个问题的不同算法，其程序运行时间一般不同。一个好的算法运行时间较少。算法自身的好坏对运行时间的影响是根本的和起决定作用的。例如，使用不同的排序算法对同一组元素进行排序，程序运行的时间通常是不相同的。

程序的一次运行是针对所求解问题的某一特定实例（instance）而言的。例如，执行一个排序算法，需要输入一组待排序的元素，对该组特定元素的排序是排序问题的一个实例。待排序的元素个数是一个排序问题实例的重要特征（characteristics），它直接影响排序算法的执行时间和所需的存储空间。因此，分析算法性能需要考虑的一个基本特征是问题实例的规模（size）。使用同一个排序算法对100个整数进行排序与对10000个整数进行排序所需的时间很显然是不同的。

问题的规模一般是指输入数据的量，必要时也考虑输出数据的量。对于两个m×n矩阵加法问题的规模，通常考虑输入矩阵的元素个数，它正比于m×n；但对于一个由计算机随机生成并打印一个矩阵的算法来说，其运行时间与所生成的矩阵元素的个数有关，即与输出数据的量有关。还有一种情况，例如，现代密码算法需要进行超过200位长度的十进制数运算，显然算法的运行时间与输入（输出）数据的数值大小有关，此时，问题的规模必须考虑数据的数值大小。设x是这样的数，可以考虑以x的二进制形式表示的比特数b=logx+1（本书使用logn表示以2为底的对数log2n。）来度量x的数据量。数据的总输入量可以用各个数的长度之和来计算。

如果在同一个计算机系统上运行同一个程序，问题实例的规模也相同，则运行时间是否就一定相同呢？一个熟悉的例子是使用冒泡排序算法分别对100个已从小到大有序的整数排序，以及对随机选择的100个整数进行排序，它们所需的排序时间通常是不同的。这就是说，问题的规模相同，输入数据的状态（如排列次序）不同，所需的时间开销也会不同。

2.1.3 算法的时间复杂度

1.抽象机模型

从上面讨论可以看到，一个程序运行的时间与计算机系统的性能有关。为了消除计算机因素对算法分析的影响，现假定算法（程序）运行在一台抽象的计算机模型上，它不依赖于实际的计算机软、硬件系统。设抽象机提供由m个基本运算（也可称为语句）组成的运算集O={O1, O2, …, Om}，每个运算都是基本的，它们的执行时间是有限常量。同时设执行第i个运算Oi所需的时间是ai，1≤i≤m。因此，一个算法对于给定输入在抽象机上的一次执行过程，表现为执行一个基本运算的序列。

2.时间复杂度

一个算法的时间复杂度（time complexity）是指算法运行所需的时间。

设有一个在抽象机上运行的算法A，I是某次运行时的输入数据，其规模为n，则算法A的运行时间T是n和I的函数，记做T(n, I)。又设在该次运算中抽象机的第i个基本运算Oi的执行次数为βi，1≤i≤m，βi也是n和I的函数，记做βi(n, I)。那么，算法A在输入为I时的运行时间是：

这就是算法的时间复杂度。式中，输入数据I代表问题的一个实例，n是问题的规模。

3.最好、最坏和平均时间复杂度

前面提到，对于许多算法，即使问题的规模相同，如果输入数据I不同，算法所需的时间开销也会不同。

例如，在一个有n个元素的数组中查找一个指定元素，某个搜索算法从第一个元素开始，一次检查一个数组元素。如果待查元素恰好是第一个元素，则所需的查找时间最短，这就是算法的最好情况（best case）。如果待查元素是最后一个元素，所需的查找时间最长，则是算法执行时间的最坏情况（worst case）。如果需要多次在数组中查找元素，并且假定以某种概率查找每个元素，最典型的是以相等概率查找每个元素，在这种情况下，就会发现算法需平均检索约n/2个元素，这是算法时间代价的平均情况（average case）。

本书使用B(n)、W(n)和A(n)分别表示算法的最好、最坏和平均情况时间复杂度。设I∈Dn，Dn是规模为n的所有合法输入的集合，并设I'和I*分别是Dn中使得算法运行有最好和最坏情况的实例（输入数据），P(I)是实例I（I∈Dn）在具体应用中被使用的概率，则算法的上述三种情况时间复杂度可分别定义如下：

这三种时间复杂度从不同角度反映算法的效率，各有用途，也各有局限性。其中，比较容易分析和计算，并且也最有实际价值的是最坏情况时间复杂度。在本书中，算法分析的重点也主要集中在对最坏情况时间复杂度的分析和计算上。

还有一种类型的时间效率称为分摊效率。它并不针对算法的单次运行，而是计算算法在同一数据结构上执行一系列运算的平均时间。也许单次运算的时间代价较高，但n次运算的总运行时间除以n的平均时间效率并不差，这就是分摊效率。关于分摊效率将在稍后做深入讨论。

2.1.4 使用程序步分析算法

从上面讨论可知，程序运行时间不仅与算法的优劣和输入数据直接相关，还与运行程序的计算机软、硬件环境有关。为了分析算法的效率，总希望略去计算机系统因素，对算法自身的特性进行事前分析（priori analysis），即在算法实际运行前分析算法的效率。这种分析结果显然不可能是程序运行时间的具体值，而是运行时间的一种事前估计。算法的事后测试（posteriori testing）是通过运行程序，测试一个程序在所选择的输入数据下实际运行所需要的时间。

前面关于算法时间复杂度的概念是在抽象机模型上定义的。对于用程序设计语言书写的算法，应如何分析其时间复杂度呢？可以设想，如果我们将程序设计语言中的循环语句的执行过程，视为其循环体（其中不嵌套循环）的重复执行过程，并对每次函数调用单独计算它的时间。那么，就可将抽象机模型上定义的概念用于分析由具体程序设计语言描述的算法。对于用C/C++语言描述的算法，可将每种可执行语句（除循环语句外）看成一种基本运算；对于循环语句，需计算其循环体的执行次数。这就可以通过一个算法在给定输入下所执行的总的语句条数来计算算法的时间复杂度。下面定义的程序步概念可进一步简化算法分析。它并不直接计算总的语句执行条数，而是将若干条语句合并成一个程序步来计算。

一个程序步（program step）是指在语法上或语义上有意义的程序段，该程序段的执行时间必须与问题实例的规模无关。

现以程序2-1求数组元素之和为例来说明如何计算一个算法的程序步数。设n个元素存放在一维数组list中，count是全局变量，用来计算总的程序步数。在程序中，语句count++;与数组求和的算法无关，只是为了计算程序步数而添加的。忽略所有count++;语句，便是一个数组求和程序。可以看到，这里被计算的每一程序步的执行时间，均与问题实例的规模n（数组元素的个数）无关。该程序的总程序步数为2n+3。

【程序2-1】 求数组元素累加之和的迭代程序

float Sum(float list[], const int n)
{
     float tempsum=0.0;
     count ++; //针对赋值语句
     for (int i=0; i<n; i++){
          count ++; //针对for循环语句
          tempsum+=list[i];
          count ++; //针对赋值语句
     }
     count ++; //针对for的最后一次执行
     count ++; //针对return语句
     return tempsum;
}

程序2-2是求数组元素之和的递归程序。为了确定这一递归程序的程序步，首先考虑当n=0时的情况。很明显，当n=0时，程序只执行if条件判定和第二个return语句，所需的程序步数为2。当n＞0时，程序在执行if条件判定后，将执行第一个return语句。此return语句不是简单返回，而是在调用函数RSum(list,n-1)后，再执行一次加法运算后返回。读者同样可以移去程序RSum中所有count++;语句，得到一般的数组求和递归程序。

设RSum(list,n)的程序步为T(n)，RSum(list,n-1)的程序步为T(n-1)，那么，当n＞0时，T(n)=T(n-1)+2。于是有：

这是一个递推关系式，它可以通过转换成如下和式来计算：

T(n)=2+T(n-1)=2+2+T(n-2)

=2×3+T(n-3)

…

=2×n+T(0)

=2×n+2

虽然从表面看来，程序RSum所需的程序步为2n+2，少于程序Sum的程序步2n+3，但这并不意味着前者比后者快，这是因为两者使用的程序步是不同的。递归调用引起的循环计算和使用for语句的循环计算所需的开销是不同的，递归需要耗费更多的时间和空间资源。有关递归算法及其分析方法将在本章稍后及以后章节中做进一步讨论。

【程序2-2】 求数组元素累加之和的递归程序

float RSum(float list[], const int n)
{
  count ++; //针对 if 条件
  if (n){
    count++; //针对 RSum 调用和return语句
    return RSum(list, n-1)+list[n-1];
  }
  count++; //针对return语句
  return 0;
}

2.1.5 算法的空间复杂度

一个算法的空间复杂度（space complexity）是指算法运行所需的存储空间。程序运行所需的存储空间包括以下两部分。

（1）固定空间需求（fixed space requirement）：这部分空间与所处理数据的大小和个数无关，也就是说，与问题实例的特征无关，主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。

（2）可变空间需求（variable space requirement）：这部分空间大小与算法在某次执行中处理的特定数据的规模有关。例如，分别包含100个元素的两个数组相加，与分别包含10个元素的两个数组相加，所需的存储空间显然是不同的。这部分存储空间包括数据元素所占的空间，以及算法执行所需的额外空间，例如，运行递归算法所需的系统栈空间。

对算法空间复杂度的讨论类似于时间复杂度，并且一般来说，空间复杂度的计算比起时间复杂度的计算容易。此外，应当注意的是，空间复杂度一般按最坏情况来分析。

2.2 渐近表示法

引入程序步的目的在于简化算法的事前分析。正如前面已经讨论过的，不同的程序步在计算机上的实际执行时间通常是不同的，程序步数并不能确切反映程序运行的实际时间。而且事实上，一个程序在一次执行中的总程序步的精确计算往往也是困难的。那么，引入程序步的意义何在？本节中定义的渐近时间复杂度，使得有望使用程序步在数量级上估计一个算法的执行时间，从而实现算法的事前分析。

2.2.1 大O记号

定义2-1 设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≤cg(n)，则记做f(n)=O(g(n))，称为大O记号（big Oh notation）。

大O记号可以看成n的函数的集合。O(g(n))表示所有增长阶数不超过g(n)的函数的集合，它用以表达一个算法运行时间的上界。称一个算法具有O(g(n))的运行时间，是指当n足够大时，该算法在计算机上的实际运行时间不会超过g(n)的某个常数倍，g(n)是它的一个上界。

例2-1 f(n)=2n+3=O(n)

当n≥3时，2n+3≤3n，所以，可选c=3，n0=3。对于n≥n0，f(n)=2n+3≤3n，所以，f(n)=O(n)，即2n+3∈O(n)。这意味着，当n≥3时，程序2-1的程序步不会超过3n，2n+3=O(n)。

例2-2 f(n)=10n2+4n+2=O(n2)

对于n≥2时，有10n2+4n+2≤10n2+5n，并且当n≥5时，5n≤n2，因此，可选c=11, n0=5；对于n≥n0，f(n)=10n2+4n+2≤11n2，所以f(n)=O(n2)。

例2-3 f(n)=n！=O(nn)

对于n≥1，有n(n-1)(n-2) … 1≤nn，因此，可选c=1，n0=1。对于n≥n0，f(n)= n！≤nn，所以，f(n)=O(nn)。

例2-4 10n2+9≠O(n)

使用反证法，假定存在c和n0，使得对于n≥n0，10n2+9≤cn始终成立，那么有10n+9/n≤c，即n≤c/10-9/(10n)总成立。但此不等式不可能总成立，取n=c/10+1时，该不等式便不再成立。

上面的例子也表明这样的事实，即对于给定的f，可有无数个g与之对应。例如，f(n)=2n+3，g可以是：n，n2，n3，…。在算法分析中，应当选择最小的函数g作为f的上界。

定理2-1 如果f(n)=amnm+am-1nm-1+…+a1n+a0是m次多项式，且am＞0，则f(n)=O(nm)。

证明：取n0=1，当n≥n0时，有

可取c=|am|+|am-1|+…+|a1|+|a0|，定理得证。

假定一个程序的实际执行时间T(n)=3.6n3+2.5n2+2.8，以上定理表明T(n)=O(n3)。这就是说，如果只能知道一个算法的时间是T(n)=O(n3)，虽然并不能得到T(n)=3.6n3+2.5n2+2.8这一精确计算公式，但从算法事前分析的角度，可以认为已经有了对算法时间复杂度上界的满意的估计值。

使用大O记号及下面定义的几种渐近表示法表示的算法时间复杂度，称为算法的渐近时间复杂度（asymptotic complexity）。渐近时间复杂度也常简称为时间复杂度。记号O(1)用于表示常数计算时间，它代表算法只需执行有限个程序步。

在很多情况下，可以通过考察一个程序中关键操作（key operation）的执行次数，来估算算法的渐近时间复杂度。有时也需要同时考虑几个关键操作，以反映算法的执行时间。例如，程序2-1中，语句tempsum+=list[i];可被认为是关键操作，它的执行次数为n，与总的程序步2n+3有相同的渐近时间复杂度O(n)。

只要适当选择关键操作，算法的渐近时间复杂度可以由关键操作的执行次数之和来计算。一般，关键操作的执行次数与问题的规模有关，是n的函数。在很多情况下，它是算法中执行次数最多的操作（程序步）。关键操作通常是位于算法最内层循环的程序步（或语句）。

程序2-3是实现两个n×n矩阵相乘的程序段，每行最右边注明该行语句执行的次数，即作为程序步看待。对于循环语句for (i=0; i<n; i++) {y;}，可以认为循环体y执行n次，而for自身执行n+1次比较运算（i＜n）。因此，程序中所有语句的执行次数为T(n)=2n3+3n2+2n+1。由定理2-1可知，程序2-3的渐近时间复杂度为O(n3)。如果将语句c[i][j]+=a[i][k]*b[k][j];看成关键操作，它的执行次数是n3，从它同样可以得到O(n3)。

【程序2-3】 矩阵乘法

for（i=0; i<n; i++） //n+1
   for（j=0; j<n; j++）{ //n(n+1)
     c[i][j]=0; //n2
     for（k=0; k<n; k++） //n2(n+1)
          c[i][j]+=a[i][k]*b[k][j]; //n3
     }

有时，算法的时间计算并非直截了当。例如，程序1-2求最大公约数递归算法的运行时间是多少？虽然看起来余数的值在减小，却并不是按常数因子递减的。定理2-2表明，两次迭代以后，余数最多是原始值的一半。这就证明了迭代次数最多为2logm=O(logm)，所以欧几里得算法的时间复杂度为O(logn+logm)。

定理2-2 如果n＞m，则n mod m＜n/2。

证明：如果m≤n/2，则由于余数小于m，故定理在这种情形下成立。当m＞n/2时，n-m＜n/2，定理得证。

2.2.2 W记号

定义2-2 设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数 c和n0，使得当n≥n0时，有f(n)≥c g(n)，则记做f(n)=Ω(g(n))，称为Ω记号（omega notation）。

Ω记号可以看成n的函数的集合。Ω(g(n))表示所有增长阶数不低于g(n)的函数的集合，它用于表示一个算法运行时间的下界。称一个算法具有Ω(g(n))的运行时间，是指当n足够大时，该算法在计算机上运行，至少需要g(n)的某个常数倍大小的时间量。

例2-5 f(n)=2n+3=Ω(n)

对所有n，2n+3≥2n，可选c=2，n0=0。对于n≥n0，f(n)=2n+3≥2n，所以，f(n)=Ω(n)，即2n+3∈Ω(n)。

例2-6 f(n)=10n2+4n+2=Ω(n2)

对所有n，10n2+4n+2≥10n2，可选c=10，n0=0。对于n≥n0，f(n)=10n2+4n+2≥10n2，所以，f(n)=Ω(n2)。

与大O记号类似，对于给定f，可有无数个g与之对应。例如，f=10n2+4n+2，g可以是n2，n1，n1/2，…。应当选择最接近的函数g，即f的最大下界。

定理2-3 如果f(n)=amnm+am-1nm-1+…+a1n+a0是m次多项式，且am＞0，则f(n)=Ω( nm)。

证明留做练习。

本章一开始提到了在n个元素的集合中求最大元素的问题。直观地考虑，我们可以设计一个算法，通过对集合中的元素进行比较，最终确定最大元素。元素间的比较运算显然是这一算法的关键操作。能够初步断定，对于求解这一问题的任意正确算法，至少需做n-1次比较，才能求得最大元素。因为假如比较次数不足n-1次，那么很显然，至少有一个元素未和其他元素做过比较，这样的算法不可能是正确的。因此，f(n)≥n-1=Ω(n)。这里，十分有意义的是，Ω(n)不仅是具体某一个求最大元素算法的时间下界，它也是求最大元素问题的时间下界。这就是算法的最优性问题。

2.2.3 Θ记号

定义2-3 设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正常数c1，c2和n0，使得当n≥n0时，有c1g(n)≤f(n)≤c2 g(n)，则记做f(n)=Θ(g(n))，称为Θ记号（Theta notation）。

Θ记号可以看成n的函数的集合。Θ(g(n))表示所有增长阶数与g(n)相同的函数的集合，它用于表示一个算法运行时间具有与g(n)相同的阶。称一个算法具有Θ(g(n))的运行时间，是指当n足够大时，该算法在计算机上的实际运行时间大约为g(n)某个常数倍大小的时间量。从上两节讨论可知，下面例2-7和例2-8的结论成立。

例2-7 f(n)=2n+3=Θ(n)，即2n+3∈Θ(n)。

例2-8 f(n)=10n2+4n+2=Θ(n2)。

定理2-4 如果f(n)=amnm+am-1nm-1+…+a1n+a0是m次多项式，且am＞0，则f(n)=Θ(nm)。

证明留做练习。

2.2.4 小o记号

定义2-4 f(n)=o(g(n))当且仅当f(n)=O(g(n))且f(n)≠Ω(g(n))

小o记号（little Oh notation）可以看成n的函数的集合。o(g(n))表示所有增长阶数小于g(n)的所有函数的集合，它用于表示一个算法运行时间f(n)的阶比g(n)低。从上面的讨论可知，例2-9的结论成立。

例2-9 f(n)=2n+3=o(n2)，即2n+3∈o(n2)。

2.2.5 算法按时间复杂度分类

算法可以按计算时间分成两类：凡渐近时间复杂度为多项式时间限界的算法称做多项式时间算法（polynomial time algorithm），而渐近时间复杂度为指数函数限界的算法称做指数时间算法（exponential time algorithm）。

最常见的多项式时间算法的渐近时间复杂度之间的关系为：

O(1)＜O(log n)＜O(n)＜O(nlog n)＜O(n2)＜O(n3)

最常见的指数时间算法的渐近时间复杂度之间的关系为：

O(2n)＜O(n！)＜O(nn)

随着n的增大，指数时间算法和多项式时间算法在所需的时间上非常悬殊。表2-1和图2-1显示了几种典型的时间函数随问题规模增长的情况。

表2-1 时间复杂度函数增长情况

从图2-1中可以看到，O(log n)、O(n)和O(nlog n)的增长比较平稳，指数函数2n的曲线非常陡。实际情况是，对大的n值，在目前一般计算机上，运行一个复杂度高于O(nlog n)的算法已经很困难了。对于指数时间算法，只有当n很小时才有实用价值。

假定计算机执行每条语句的时间是相等的，都是1毫秒，那么1小时可以执行3.6×106条语句。如果要求算法的执行时间不超过1小时，那么，对于一个时间复杂度为nlogn的算法，所能处理的问题的规模约可达2.0×105；而对于时间复杂度为2n的算法，情况就糟得多，在1小时内算法只能处理n不超过21的小问题。如果将计算机速度提高1万倍，那么，对于时间复杂度是nlogn的算法，能处理的问题规模可以从n大约提高到9000n；但对于有指数时间2n的算法，所能处理的问题规模只能增加到n+13.3左右。这就是说，提高计算机速度，可以较大幅度地增加具有线性或nlogn时间算法所能处理的问题的能力，但对指数时间算法的收效甚微。

对算法进行时间分析，是为了尽可能降低算法时间复杂度的数量级。上述讨论表明，为了提高程序运行速度，选择一种更快的算法比换一台更快的机器奏效。

2.3 递推关系

2.3.1 递推方程

递推关系经常用来分析递归算法的时间和空间代价。分析一个递归算法的时间一般需要列出关于时间复杂度函数的递推关系式。

递推方程（recurrence equation）是自然数上一个函数T(n)，它使用一个或多个小于n时的值的等式或不等式来描述。递推方程也称为递推关系或递推式。第2.1.4节中的式（2-5）就是对于程序2-2的时间分析的递推方程。

递推方程必须有一个初始条件（也称边界条件），式（2-5）中的T(0)=2就是该递推方程的初始条件。有时需要给定的初始条件不一定是当n=0时的值，也可以使用n=1或n=2等其他小的n值作为递推方程的初始值。

例2-10 程序1-5的时间分析

设n=d1d2…dk是k位数，当k=1时，只执行cout语句和if判定语句；当n至少是2位数（k＞1）时，除了执行这两个操作外，还需执行递归函数调用PrintDigit(n/10)，是k-1位数，于是得到式（2-6）的递推式：

可以采用与式（2-5）相同的方法，将其转换成和式来计算。这种方法称为迭代方法。从式（2-5）可知式（2-6）的计算结果是：

T(k)=2k+2=Θ(k)

计算递推式通常有三种方法：迭代方法（iterating）、替换方法（substitution）和主方法（master method）。

迭代方法通过扩展递推，把递推式先转换成一个和式，然后使用求和技术进行计算。替换方法需要先猜测递推式的解（渐近复杂度的上、下界），然后使用归纳法证明该上、下界，还可能需要进一步做收缩，得到最接近的上、下界。主方法是对算法分析中一类典型的递推式T(n)= aT(n/b)+f(n)，利用已经证明的主定理直接得到渐近复杂度的方法。

一般来说，问题的规模是非负整数，而且对足够小的问题，算法的运行时间可视为常量，所以，在以后讨论中，当描述递推式时，如果没有明确指明，则都假定n是非负整数，并假定对足够小的n值，T(n)是常量。

2.3.2 替换方法

替换方法要求首先猜测递推式的解，然后用归纳法证明。下面使用替换方法计算汉诺塔问题的递推式。

例2-11 使用替换方法分析程序1-6

分析汉诺塔问题，得到递推式：T(1)=1, T(n)=2T(n-1)+1。可以先对以下这些小的示例进行计算：

T(3)=7=23-1；T(4)=15=24-1；T(5)=31=25-1；T(6)=63=26-1

看起来，似乎T(n)=2n-1，n≥1，下面再用归纳法证明这一结论。

证明：（归纳法证明）

当n=1时，T(1)=1，结论成立。归纳法假设：当k＜n时，有T(k)=2k-1，那么，当k=n时，T(n)=2T(n-1)+1=2(2n-1-1)+1=2n-1。因此，对所有n≥1，T(n)=2n-1=Θ(2n)。

2.3.3 迭代方法

迭代方法的思想是扩展递推式，将递推式先转换成一个和式，然后计算该和式，得到渐近复杂度。它需要较多的数学运算。

例2-12 使用迭代方法分析程序1-6

函数Hanoi中两次调用自身，函数调用使用的实在参数均为n-1，函数Move所需时间具有常数界Θ(1)，可以将其视为一个程序步，于是有：

扩展并计算此递推式：

T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=22T(n-2)+2+1

=23T(n-3)+22+2+1

…

=2n-1T(1)+…+22+2+1=2n-1+…+22+2+1=2n-1

汉诺塔问题也称梵天塔问题（tower of Brahma）。相传印度教的天神梵天在创造地球时，建了一座神庙，神庙中有三根柱子，第一根柱子上从小到大套着64个金盘，形成所谓的梵天塔。天神让僧侣们按照前面介绍的规则，将64个金盘从第一根柱子，借助第二根柱子移到第三根柱子。天神断言，移完的那一天就是世界末日。从上面的计算可知，当n=64时，要完成梵天塔搬迁需要移动盘子的次数为：264-1=18446744073709551615。如果每秒移一次，需要500亿年以上。这也使我们看到，指数时间算法仅对规模很小的问题是可用的。

使用递归树（recursion tree）可以形象地看到递推式的迭代过程。下面举例说明对给定的递推方程，通过构造递归树来求解的方法。

例2-13 T(n)=2T(n/2)+n的递归树

为方便起见，假定n是2的整数幂。图2-2显示该递推方程的递归树的导出过程。递归树上每个结点有两个域：递归式T(n)和非递归的代价，n是问题规模。本例中，根结点时的规模为n，本例的非递归代价恰好也是n。根结点扩展两棵子树，因此，第二层有两个结点，规模为n/2，非递归代价各为n/2。继续这一扩展过程，直到达到初始条件（边界条件）。图2-2的递归树高度（层数）为logn+1，每一层的非递归代价之和均为n。现将树中所有层的代价加起来便得到递推方程的解为Θ(nlogn)。

例2-14 T(n)=T(n/3)+T(2n/3)+n的递归树

例2-14给出了另一个更复杂的例子，图2-3是其对应的递归树。从根到叶的最长的一条路径是n→(2/3)n→(2/3)2n→…→1。因为(2/3)kn=1，k=log3/2n，该树的高度（层数）为log3/2n+1。因而，此递推方程的解至多是n(log3/2n+1)=O(nlogn)。

2.3.4 主方法

在递归算法分析中，常需要求解如下形式的递推式：

T(n)=aT(n/b)+f(n) （2-8）

式中，a≥1和b＞1是常数，f(n)是一个渐近正函数，n/b指或。

求解这类递推式的方法称为主方法。主方法依赖于下面的主定理，使用主定理可直接得到递推式的解。关于主定理的证明见文献[2]。

定理2-5 （主定理）设a≥1和b＞1为常数，f(n)是一个函数，T(n)由下面的递推式定义

T(n)=aT(n/b)+f(n)

式中，n/b指或，则T(n)有如下的渐近界：

（1）若对某常数＞0，有f(n)=O()，则T(n)=Θ()；

（2）若f(n)=Θ()，则T(n)=Θ(logn)；

（3）若对某常数＞0，有f(n)=Ω()，且对某个常数c＜1和所有足够大的n，有af(n/b)≤cf(n)，则T(n)=Θ(f(n))。

需要注意的是，主定理的三种情况并没有覆盖所有的f(n)，存在某些f(n)不满足以上任何一种情况的条件，则此时就不能用主方法求解递推式。下面通过几个例子介绍主定理的应用。

例2-15 T(n)=16T(n/4)+n

因为a=16, b=4,=n2, f(n)=n=O()=O)，其中，=1与主定理的情况（1）相符合，T(n)=Θ()=Θ(n2)。

例2-16 T(n)=T(3n/7)+1

因为a=1, b=7/3,==n0=1, f(n)=1=Θ()，所以，符合主定理情况（2），T(n)=Θ(logn)=Θ(logn)。

例2-17 T(n)=3T(n/4)+n logn

因为a=3, b=4,，其中，≈0.2。由于对足够大的n，3(n/4)log(n/4)≤(3/4)nlogn，这里c=3/4，符合主定理情况（3）。T(n)=Θ(f(n))=Θ(nlogn)。

并非所有递推式都可用主定理求解，主定理对例2-18的递推式并不适用。

例2-18 T(n)=2T(n/2)+nlogn

由于a=2, b=2, f(n)=nlogn和=n。看起来似乎属于主定理情况（3），但事实上不是。因为f(n)只是渐近大于n，但并不是多项式大于n。f(n)与的比值是log n，对于任何正数，log n渐近小于，所以，此例不能运用主定理。

2.4 分摊分析

在很多情况下，对一个数据结构的操作往往不是单独执行一次运算，而是重复多次执行多个运算，形成一个运算执行序列。如果执行n个运算的总时间为T(n)，则每个运算的平均代价（average cost）为T(n)/n，分摊分析的目的是求平均代价。

分摊分析（amortized analysis）是对一个长的运算序列所需的最坏情况时间求平均值。设在最坏情况下，对所有n，执行一个长度为n的运算序列所需的最坏情况时间为T(n)，那么，每个运算平均代价为T(n)/n。

分摊分析和平均情况分析的不同之处在于它不需要假定每个运算的概率，因而不涉及概率。分摊分析保证在最坏情况下一个运算序列中每个运算的平均性能。

分摊分析一般有三种方法：聚集方法、会计方法和势能方法。

2.4.1 聚集方法

聚集方法（aggregate analysis）中需要对所有n，计算由n个运算构成的运算序列在最坏情况下总的执行时间T(n)，则每个运算的平均代价为T(n)/n。请注意，序列中允许包含不同种类的运算，但每个运算的分摊代价是相同的。

例2-19 设堆栈上定义了两个运算：void Push(T x)和T Pop()，T是元素类型，前者将对象x进栈，后者从栈中弹出并返回栈顶元素。已知这两种运算的时间都是O(1)，不妨假定每个运算的程序步数（即代价）是1。这样，执行一个包含n次运算的序列的总代价为n，其运行时间为Θ(n)，因此，每个运算的平均代价为T(n)/n=Θ(n)/n=Θ(1)。计算中没有用到概率。

例2-20 设在上例的栈数据结构上定义一个新运算void MultiPop(int k)，该运算从栈中连续弹出k个元素。

现在来分析从空栈开始，执行一个包括n个Push、Pop和MultiPop构成的运算序列的最坏情况时间。很显然，MultiPop运算的最坏情况时间是O(n)，因为在执行n次栈运算中，栈的大小最多为n。那么，能否因此认为一个包含n次栈运算的序列，在最坏情况下的总时间是O(n2)，从而得到每个栈运算在最坏情况下的平均时间为O(n)呢？虽然这样分析是正确的，但不够精确。下面的聚集分析将获得一个更精确的上界。

事实上，从初始空栈开始，任意一个包含n个Push、Pop和MultiPop运算的执行序列总的程序步至多是n步。这是很显然的，因为每压入一个元素，至多可弹出一个元素。在一个非空栈上执行Pop和MultiPop时，被弹出的元素总数不超过Push的执行次数。因此，对任意n，一个包含n个栈运算的序列的总执行时间为O(n)，因而每个运算的平均代价为O(n)/n=O(1)。

2.4.2 会计方法

对于给定的数据结构，会计方法（accounting method）对每个运算预先赋予不同的费值（charge）。其中，某些运算的费值可能超过它们的实际代价（actual cost），而另一些运算的费值会低于实际代价。对每个运算所记的费值称为分摊代价（amortized cost）。其超出部分如同存款（credit）一样保存起来，用于补偿以后代价不足的运算。与聚集分析不同的是，会计方法的分摊代价可以不同，而聚集分析中每个运算有相同的分摊代价。

使用会计方法，首先按预先分配给每个运算的分摊代价，计算一个运算序列的总的分摊代价。如果能够保证对所有n，任意一个运算序列的总分摊代价不会低于该运算序列的实际代价T(n)，即运算序列的总的分摊代价是总的实际代价的上界，设总分摊代价为O(g(n))，则T(n)=O(g(n))。

这就要求在一个运算序列执行的任何时刻，总分摊代价始终不低于该时刻的实际代价。如果在一个运算序列的执行中，随时记录下迄今为止的累计分摊代价减去实际代价的余额，则这一累计余额始终应当是非负的。如果在执行某个运算后，代价余额出现负值，则说明迄今为止的分摊代价低于当时消费的实际代价，这种情形表示这样计算的总分摊代价将不能作为总的实际代价的上界来计算每个运算的平均代价。请注意区分分摊代价和平均代价。

例2-21 使用会计方法分析例2-20的栈运算

会计分析首先需要精心分配每个运算的分摊代价，代价用程序步度量。表2-2列出各个栈运算的实际代价和分摊代价，其中，Min(k, m)中的k是运算MultiPop的参数，m是执行此运算时，栈中元素的个数。

表2-2 栈运算的实际代价和分摊代价

在表2-2中，对Push预分配的分摊代价为2，显然超过了此运算的实际代价，而对Pop和MultiPop分配的分摊代价都为0，低于实际代价，但事实上，MultiPop的实际代价是随参数k变化的。通过仔细分析可知，表2-2的分摊代价分配方式是可行的，因为它可以保证在执行一个运算序列的任何时刻，其代价余额不会为负值。理由是：每执行一次Push有一个程序步的节余，可用于支付一次Pop运算或MultiPop运算的一步（弹出一个元素）。由于必须执行一次Push，才有可能执行一次Pop或MultiPop的一步，因此，关于堆栈操作的总代价余额不会为负值。这样，总分摊代价O(n)必定是总实际代价的上界，T(n)=O(n)，每个运算的平均代价为T(n)/n=O(1)。

对于给定的初始数据结构，任意一个关于该数据结构的运算序列，会计方法记录运算序列中每个运算的分摊代价与实际代价之差的总和，这个量任何时刻都不能为负值。会计方法将分摊代价超过实际代价的余额用于填补分摊代价小于实际代价的运算，但总的累计余额始终不能为负值。

2.4.3 势能方法

给定一个初始数据结构，执行该数据结构上的一个运算将使该数据结构改变状态。势能方法（potential method）为数据结构的每个状态定义一个被称为势能的量。设数据结构的初始状态为D0。对D0执行一个n次运算的序列，ci是第i个运算的实际代价，Di为在数据结构的状态Di-1时执行第i个运算后得到的数据结构的新状态。势能函数Φ将数据结构的每个状态映射为一个实数Φ(Di)，称为数据结构在该状态下的势能。第i个运算的分摊代价定义为：

从上式可知，每个运算的分摊代价是其实际代价ci加上执行该运算引起的数据结构势能的增量Φ(Di)-Φ(Di-1)。那么，n个运算的总分摊代价是：

如果能够定义一个势能函数Φ，使得Φ(Dn)≥Φ(D0)，则可知总的分摊代价是总实际代价的上界。

式（2-10）定义的分摊代价依赖于势能函数，不同的势能函数可能会产生不同的分摊代价，并使得运算序列的总的分摊代价不同，但它们都是总实际代价的上界。

例2-22 使用势能方法分析例2-20的栈运算

可将栈数据结构的势能定义为栈中元素个数。初始时，栈为空栈D0，且Φ(D0)=0。由于栈中元素个数始终是非负的，故在第i个运算执行后，Di总有非负的势能，即Φ(Di)≥0。

现在来计算各栈运算的分摊代价。

（1）对于Push运算，栈中元素个数加1，即数据结构的势能加1，其分摊代价为：

（2）对于MultiPop(s, k)运算，该运算将弹出k'=min(k, m)个元素，m是当前栈中元素的个数，势能差Φ(Di)-Φ(Di-1)=-k'。由于实际弹出k'个元素，故该运算的实际代价也是k'，于是，MultiPop运算的分摊代价为：

（3）对于Pop运算，其势能差为-1，分摊代价为：

由此可见，三个栈运算的分摊代价均为O(1)，n个运算的总分摊代价就是O(n)。并且因为Φ(Dn)≥Φ(D0)=0，因此总的分摊代价是实际代价的上界，n个栈运算的最坏情况分摊代价为T(n)=O(n)，每个栈运算的平均时间为T(n)/n=O(1)。

本章小结

本章重点介绍算法分析的基本方法。算法的时间和空间效率是衡量一个算法性能的重要标准，对于算法的性能分析可以采用事前分析和事后测量形式进行。算法分析通常是指使用渐近表示法对一个算法的时间和空间需求做事前分析。算法复杂度的渐近表示法用于在数量级上估算一个算法的时空资源耗费。算法的运行时间可使用程序步来衡量。一个算法可以讨论其最好、平均和最坏情况时间复杂度，其中，最坏情况分析最有实际价值。算法的空间复杂度一般只做最坏情况分析。

递归算法是一类重要的算法结构，也是较难掌握的一种算法技术。在第1章基础上，本章讨论使用递推关系分析递归算法的方法及求解递推式的3种途径。最后讨论算法时间分析的分摊方法。

习题2

2-1 简述衡量一个算法的主要性能标准。说明算法的正确性和健壮性的关系。

2-2 什么是算法的最优性？

2-3 简述影响一个程序运行时间的因素。

2-4 什么是算法的时间复杂度和空间复杂度？什么是最好、平均和最坏情况时间复杂度？

2-5 什么是算法的事前分析，什么是事后测试？

2-6 什么是程序步？引入程序步概念对算法的时间分析有何意义？

2-7 什么是多项式时间算法？什么是指数时间算法？

2-8 确定下列各程序段的程序步，确定画线语句的执行次数，计算它们的渐近时间复杂度。

（1）i=1; x=0;

do{
x++; i=2*i;
} while i<n;

（2）for(int i=1; i<=n; i++)

       for(int j=1; j<=i; j++)
          for (int k=1; k<=j; k++) x++;

（3）x=n; y=0;

     while(x>=(y+1)*(y+1)) y++;

（4）m=0;

     for（int i=0; i<n; i++）
        for(int j=2*i; j<=n; j++) m++;

2-9 矩阵转置

（1）设计一个C/C++程序实现一个n×m的矩阵转置。原矩阵及其转置矩阵保存在二维数组中。

（2）使用全局变量count（类似程序2-1的做法），改写矩阵转置程序，并运行修改后的程序以确定此程序所需的程序步。

（3）计算此程序的渐近时间复杂度。

2-10 试用定义证明下列等式的正确性。

（1）5n2-8n+2=O(n2)

（2）5n2-8n+2=Ω(n2)

（3）5n2-8n+2=Θ(n2)

2-11 设有f(n)和g(n)如下所示，分析f(n)为O(g(n))、Ω(g(n))还是Θ(g(n))。

（1）f(n)=20n+logn，g(n)=n+log3n

（2）f(n)=n2/logn，g(n)=nlog2n

（3）f(n)=(logn)logn，g(n)=n/logn

（4）f(n)=，g(n)=log5n

（5）f(n)=n2n，g(n)=3n

2-12 将下列时间函数按增长率的非递减次序排列：

(3/2)n，，log2n，nlogn，n！，log(logn), 2n，n1/logn，n2

2-13 设f1(n)=O(g1(n))，f2(n)=O(g2(n))，证明下列结论成立。

（1）f1(n)+f2(n)=O(max{g1(n)，g2(n)})

（2）f1(n)+f2(n)=O(g1(n)-g2(n))

2-14 证明：若f(n)=amnm+am-1nm-1+…+a1n+a0是m次多项式，且am＞0，则f(n)=Ω(nm)。

2-15 证明：若p(n)是n的多项式，则O(log(p(n))=O(logn)。

2-16 使用递推关系式计算求n！的递归函数的时间，要求使用替换和迭代两种方法分别计算之。

2-17 设T(n)由如下递推式定义，证明T(n)=O(nlog2(n))。

2-18 假定n是2的幂，T(n)由如下递推式定义，计算T(n)的渐近上界。

2-19 利用递归树计算递推方程T(n)=2T(n/2)+n2，T(1)=2。

2-20 使用下列数据计算主定理的递推式：

（1）a=1, b=2, f(n)=cn

（2）a=5, b=4, f(n)=cn2

（3）a=28, b=3, f(n)=cn3

2-21 运用主定理计算T(n)=2T(n/4) +, T(1)=3的渐近界。

2-22 设对某一数据结构执行包括n个运算的运算序列。若i是2的整数幂，则第i次运算的代价为i，否则为1。请使用聚集方法确定每次运算的代价。

2-23 利用会计方法重做上一题。

2-24 设有一个大小为k的栈，每执行k次运算后总要执行一次复制运算，将整个栈的内容复制保存。证明：对每种栈运算赋予适当的分摊代价后，n个栈运算（含复制栈运算）的代价为O(n)。

2-25 用势能方法重做习题2-22。

2-26 假设一个栈在执行n次栈运算Push、Pop和MultiPop之前有s0个元素，执行运算序列后有sn个元素，则n个栈运算的总代价是多少？

2-27 说明如何用一个普通栈来实现一个队列，使得每个Append（入队列）和Serve（出队列）运算的分摊代价均为O(1)。