1.2 算法复杂性分析

算法复杂性的高低体现运行该算法所需计算机资源的多少。算法的复杂性越高，所需的计算机资源越多；反之，算法的复杂性越低，所需的计算机资源越少。

计算机资源，最重要的是时间资源与空间资源。因此，算法的复杂性有时间复杂性与空间复杂性之分。需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。时间复杂度与空间复杂度集中反映算法的效率。

算法分析是指对算法的执行时间与所需空间的估算，定量给出运行算法所需的时间数量级与空间数量级。

1.2.1 时间复杂度

算法作为计算机程序设计的基础，在计算机应用领域发挥着举足轻重的作用。一个优秀的算法可以运行在计算速度比较慢的计算机上求解问题，而一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需求。因此，在计算机程序设计中，算法设计往往处于核心地位。如何去设计一个适合特定应用的算法是众多技术开发人员所关注的焦点。

1．算法分析的方法

要想充分理解算法并有效地应用算法求解实际案例，关键是对算法的分析。通常我们可以利用实验对比方法、数学方法来分析算法。

实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，哪个算法的速度更快我们一般就会认为这个算法性能更优。

数学方法能更为细致地分析算法，能在严密的逻辑推理基础上判断算法的优劣。但在完成实际项目过程中，我们很多时候都不能去做这种严密的论证与推断。因此，在算法分析中，我们往往采用能近似表达性能的方法来展示某个算法的性能指标。例如，当参数n比较大的时，计算机对n2和n2+2n的响应速度几乎没有什么区别，我们便可直接认为这两者的复杂度均为n2。

在分析算法时，隐藏细节的数学表示方法为大写字母“O”记法，它可以帮助我们简化算法复杂度计算的许多细节，提取主要成分，这和遥感图像处理中的主成分分析思想相近。

2．运算执行频数

一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总语句（运算）的数量级决定。

就算法分析而言，一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。

例1-2 试计算下面三个程序段的执行频数。

（1）x=x+1; s=s+x;

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

      { x=x+y;

        y=x+y;

        s=x+y;

      }

（3）for(t=1, k=1; k<=n; k++)

      { t=t*2;

        for(j=1;j<=t;j++)

          s=s+j;

      }

解：如果把以上3个程序段看成3个相应算法的主体，我们来看3个算法的执行频数。

在（1）中，2个语句各执行1次，共执行2次。

在（2）中，“k=1”执行1次；“k<=n”与“k++”各执行n次；3个赋值语句，每个赋值语句各执行n次；共执行5n+1次。

在（3）中，“t=1”与“k=1”各执行1次；“k<=n”与“k++”各执行n次；“t=t*2”执行n次；“j=1”执行n次；“j<=t”，“j++”与内循环的赋值语句“s=s+j”各执行频数为：

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

因而(3)总的执行频数为：6⋅2n+4n−4。

3．算法时间复杂度定义

算法的执行频数的数量级直接决定算法的时间复杂度。

定义对于一个数量级为f(n)的算法，如果存在两个正常数c和m，对所有的n≥m，有

则记作，称该算法具有的运行时间，是指当n足够大时，该算法的实际运行时间不会超过g(n)的某个常数倍时间。

显然，以上所列举的（1）与（2），其计算时间即时间复杂度分别为O(1), O(n) 。

据以上定义，（3）的执行频数为：6·2n+4n−4，取c=8，对任意正整数n，有

6⋅2n+4n−4≤8⋅2n

即得（3）的计算时间为O(2 )n，即（3）所代表的算法时间复杂度为O(2n) 。

可见前两个所代表的算法是多项式时间算法。最常见的多项式算法时间，其关系概括为(约定logn表示以2为底的对数)：

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

算法（3）所代表的是指数时间算法。以下3种是最常见的指数时间算法，其关系为

O(2n )<O(n! )<O(nn )

随着n的增大，指数时间算法与多项式时间算法在所需的时间上相差非常大，表1-1具体列出了常用函数时间复杂度增长情况。

一般地，当 n取值充分大时，在计算机上实现指数算法是不可能的，就是比O(nlogn)时间复杂度高的多项式算法运行也很困难。

4．符号O的运算规则

根据时间复杂度符号O的定义，有

定理1-1关于时间复杂度符号O有以下运算规则：

证明设F(n)=O( f)，根据O定义，存在常数c1和正整数n1，对所有的n≥n1，有F(n)≤c1f(n)。同样，设G(n)=O(g)，根据O定义，存在常数c2和正整数n2，对所有的n≥n2，有G(n)≤c2g(n)。

令c3=max(c1, c2), n3=max(n1, n2), h(n)=max( f, g)。对所有的n≥n3，存在c3，有

F(n)≤c1f(n)≤c3f(n)≤c3h(n)

G(n)≤c2g(n)≤c3g(n)≤c3h(n)

则 F(n)+G(n)≤2c3h(n)

即 O(f)+O(g)≤2c3h(n)=O(h)=O(max(f, g))

令t(n)=f(n)g(n)，对所有的n≥n3，有

F(n)G(n)≤c1c2t(n)

即 O(f)O(g)≤c1c2t(n)=O(fg)。

式（1.1）、式（1.2）成立。

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

证明当n≥1时，根据符号O定义有

f(n)=amnm+am−1nm−1+…+a1n+a0≤|am|nm+|am−1|nm−1+…+|a1|n+|a0|≤(|am|+|am−1|+…+|a1|+|a0|)nm

取常数c=|am|+|am−1|+…+|a1|+|a0|，根据定义，式（1.3）得证。

例1-3估算以下程序段所代表算法的时间复杂度。

for(k=1; k<=n; k++)

for(j=1; j<=k; j++)

    { x=k+j;

      s=s+x;

    }

解：在估算算法的时间复杂度时，为简单计，以后只考虑内循环语句的执行频数，而不细致计算各循环设计语句及其他语句的执行次数，这样简化处理不影响算法的时间复杂度。

每个赋值语句执行频率为1+2+…+n=n(n+1)/2，该算法的数量级为n(n+1)；取c=2，对任意正整数n，有

n(n+1)≤2 2⋅ n ⇔ n≤n 2

即得该程序段的计算时间为O( )n2 ，即所代表算法的时间复杂度为O(n2) 。

例1-4估算下列程序段所代表算法的时间复杂度。

（1）t=1; m=0;

      for(k=1; k<=n; k++)

        { t=t*2;

          for(j=t; j<=n; j++)

            m++;

        }

（2）d=0;

      for(k=1; k<=n; k++)

      for(j=k*k; j<=n; j++)

          d++;

解：（1）设n=2x，则（1）中m++语句的执行次数为：

S=(n+1−2)+(n+1−22)+(n+1−23)+…+(n+1−2x)=x(n+1)−2(2x−1)=(x−2)n+x+2

注意到x=logn，则当n≥2时有

S≤nx=n(logn)

可知（1）时间复杂度为O(nlogn)。

（2）设n=m2，则（2）中d++语句的执行次数为：

S=(n+1−12)+(n+1−22)+(n+1−32)+…+(n+1−m2)=m(n+1)−(1+22+…+m2)=m(n+1)−m(m+1)(2m+1)/6=m(6n+6−2m2−3m−1)/6

注意到，当n>3时有。

可知（2）时间复杂度为。

5．时间复杂度的其他记号

关于算法的运行时间还有Ω记号、Θ 记号与小o记号等标注。

一个算法具有Ω(g(n))的运行时间，是指当n足够大时，该算法的实际运行时间至少需要g(n)的某个常数倍时间。

例如， f(n)=2n+1=Ω(n) 。

一个算法具有Θ(g(n))的运行时间，是指当n足够大时，该算法的实际运行时间大约为g(n)的某个常数倍时间。

例如， f(n)=3n2+2n+5=Θ(n2 )。

标注o(g(n))表示增长阶数小于g(n)的所有函数的集合。f(n)=o(g(n))表示一个算法的运行时间f(n)的阶比g(n)低。

例如， f(n)=3n+2=o(n2 )。

以后在分析算法时间复杂度时对这些标记一般不作过多论述，通常只应用大O记号来标注算法的时间复杂度。

6．算法的平均情况分析

一个算法的运行时间，与问题的规模相关，也与输入的数据相关。

基于算法复杂度简化表达的思想，我们通常只对算法进行平均情况分析。对于一个给定的算法，如果能保证它的最坏情况下的性能依然不错当然很好，但是在某些情况下，程序的最坏情况算法的运行时间和实际情况的运行时间相差很大，在实际应用中几乎不会碰到最坏情况下的输入，因此通常省略对最坏情况的分析。算法的平均情况分析可以帮助我们估计程序的性能，作为算法分析的基本指标之一。

例如，对给定的n个整数a(1), a(2), …, a(n)，应用逐项比较法进行由小到大的排序，可以通过以下二重循环实现：

for(i=1; i<=n-1; i++)

for(j=i+1; j<=n; j++)

  if(a[i]>a[j])

      { h=a[i]; a[i]=a[j]; a[j]=h; }

其中3个赋值语句的执行频数之和，最理想的情形下为零（当所有n个整数已从小到大排列时），最坏情形下为3n(n−1)/2（当所有n个整数为从大到小排列时）。按平均情形来分析，其时间复杂度为O(n2)。

对于一个实用算法，我们通常不必深入研究它时间复杂度的上界和下界，只需要了解该算法的特性，然后在合适的时候应用它。

7．算法的改进与优化

为了求解某一问题，设计出复杂性尽可能低的算法是我们追求的重要目标。或者说，求解某一问题有多种算法时，选择其中复杂性最低的算法是选用算法的重要准则。

对算法的改进与优化，主要表现在有效缩减算法的运行时间与所占空间。例如，把求解某一问题的算法时间从O(n2 )优化缩减为O(nlogn)就是一个了不起的成果。或者把求解某一问题的算法时间的系数缩小，例如从2n缩小为3n/2，尽管其时间数量级都是O)(n，系数缩小了也是一个算法改进的成果。

1969年斯特拉森（V.Strassen）在求解两个n阶矩阵相乘时利用分治策略及其他的一些处理技巧，用了7次对n/2阶矩阵乘的递归调用和18次n/2阶矩阵的加减运算，把矩阵乘算法从化为O(n2.81 ) O(n3 )优，曾轰动了数学界。这一课题的研究看来并不到此止步，在斯特拉森之后，又有许多算法改进了矩阵乘法的计算时间复杂性，据悉目前求解两个 n阶矩阵相乘最好的计算时间是O(n2.376 )。

8．问题复杂性与NP完全问题

算法的复杂性是指解决问题的一个具体算法的执行时间，是衡量算法优劣的一个重要方面。而问题复杂性是指这个问题本身的复杂程度。前者是算法的性质，后者是用计算机求解问题的难易程度。

NP完全问题是“计算复杂性”研究的课题，计算复杂性是研究计算机求解问题的难度，是依据难度去研究各种计算问题之间的联系。

按问题复杂性把计算机求解问题分成以下两类。

易解问题类：可以在多项式时间内解决的判定性问题属于P(polynomial)类问题，P类问题是所有复杂度为问题规模n的多项式时间问题的集合。P类问题可以在多项式时间内解决，是易解问题类。

难解问题类：需要超多项式时间才能求解的问题看作是难处理的问题，为难解问题类。

有些问题很难找到多项式时间的算法，或许这样的算法根本不存在，或许存在只是至今尚未找到。但如果给出该问题的一个答案，可以在多项式时间内判断这个答案是否正确。这种可以在多项式时间内验证一个解是否正确的问题称为NP(nondeterministic polynomial)类问题，亦称为易验证问题类。

对于P类问题与NP完全问题，至今计算机科学界无法断定P＝NP或者P≠NP。在通常情形下，求解一个问题要比验证一个问题困难得多，因此，大多数计算机科学家认为P≠NP。

但这个问题至今尚未解决。也许使大多数计算机科学家认为P≠NP最令人信服的理由是存在一类NP完全(NP-complete, NPC)问题。这类问题有一种令人惊奇的性质，即如果一个NP完全问题能在多项式时间求解，那么其中的每一个问题都可以在多项式时间内解决。

目前已知的NPC问题已达数千个，例如背包问题、装载问题、调度问题、顶点覆盖问题、哈密顿回路问题等许多有理论意义和应用价值的优化问题都是NPC问题。

对于NPC问题，不要把它们打入“冷宫”，不要害怕继续研究。NPC问题只是极可能无法找到一个总是运行多项式时间，总能得到正确结果的精确算法。要知道，并不一定是多项式时间才快，或者说并不需要它总保持多项式时间。对于NPC问题，仍需要设计实用算法求解，以求得当数量范围比较小时的相应结果。

1.2.2 空间复杂度

算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。

一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。固定空间需求包括程序代码、常量与静态变量等所占的空间。可变空间需求包括局部作用域非静态变量所占用的空间、从堆空间中动态分配的空间与调用函数所需的系统栈空间等。

通常用算法设置的变量（数组）所占内存单元的数量级来定义该算法的空间复杂度。如果一个算法占的内存空间很大，在实际应用时该算法也是很难实现的。

先看以下3个算法的变量设置：

（1）int x, y, z;

（2）#define N 1000

    int k, j, a[N], b[3*N];

（3）#define N 100

    int k, j, a[N][3*N];

其中（1）设置三个简单变量，占用三个内存单元，其空间复杂度为O(1)。

（2）设置了两个简单变量与两个一维数组，占用4n+2个内存单元，显然其空间复杂度为O(n) 。

（3）设置了两个简单变量与一个二维数组，占用3n2+2个内存单元，显然其空间复杂度为O( )n2 。

由上可见，二维或三维数组是空间复杂度高的主要因素之一。在算法设计时，为降低空间复杂度，要注意尽可能减少高维数组的维数。

从计算机的发展实际来看，运算速度在不断增加，存储容量在不断扩大。尤其是计算机的内存，早期只有数百KB，逐步发展到MB级，现在已经达到GB级。从应用的角度看，因空间所限影响算法运行时应从精简数组入手改进空间复杂度。

空间复杂度与时间复杂度概念相同，其分析相对比较简单，在以下论述某一算法时，如果其空间复杂度不高，不至于因所占有的内存空间而影响算法实现时，通常不涉及对该算法的空间复杂度的讨论。