1.3 算法的复杂性分析

一个问题如果采用了合适的算法，其解决问题的速度将会大大提高。那么评价一个算法的好坏，主要看执行算法时需要花费的计算机CPU时间的多少和需要占用的计算机存储空间的大小。因此，算法的分析就是对其时间效率和空间效率两个方面进行比较。

这里讨论衡量算法效率的时间复杂度和空间复杂度。

1.3.1 算法评价的基本原则

算法的优劣是经过分析后得出的结果，而为判断算法的效率对其进行的分析即算法分析。但是效率分析并不是算法分析的唯一目的，虽然算法追求的目标是速度，但算法必须首先正确才有存在的意义。

不过，正确性和时间分析并不是算法分析的唯一任务，如果两个算法的时间效率是一样的，就要对算法实现的空间进行比较，空间使用较少的为优。在某些情况下，两个算法的时间、空间效率都有可能相同或相似，这时就要分析算法的其他属性，如稳定性、健壮性、实现难度等，并以此来判断到底应该选择哪一个算法。通常一个好的算法应该考虑达到以下目标。

1. 正确性

一个好的算法的前提就是算法的正确性（Correctness）。不正确的算法没有任何意义。

在给定有效输入后，算法经过有限时间的计算，执行结果满足预先规定的功能和性能要求，答案正确，就称算法是正确的。算法应当满足具体问题的需求，否则，算法的正确与否的衡量准则就不存在了。

“正确”一词的含义在通常用法上有很大差别，大体可分为四层。

（1）程序不含语法错误。

（2）程序对几组输入数据能够得出满足规格说明要求的结果。

（3）程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。

（4）程序对于一切合法的输入数据都能产生满足规格说明要求的结果。

达到第4层意义上的正确是极为困难的，所有不同输入数据的数据量大得惊人，逐一验证是不现实的，在实际上，通常以第3层意义下的正确作为一个程序是否合格的标准。

对于大型程序，可以将它分解为小的相互独立的模块，分别进行验证。而小模块程序则可以使用数学归纳法、软件形式方法等加以验证。

2. 可读性（Readability）

算法主要是为了方便用户的阅读与交流，其次才是机器的执行。因此，算法应该易于理解、调试和修改，可读性好则有助于用户对算法的理解。

3. 健壮性和可靠性

健壮性（Robustness）是指当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。即当程序遇到意外时，能按某种预定方式做出适当处理。例如，求一个凸多边形面积的算法，是采用求各三角形面积之和的策略来解决问题的。当输入的坐标集合表示的是一个凹多边形时，不应继续计算，而应报告输入错误，并且返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

正确性和健壮性是相互补充的。

程序的可靠性指一个程序在正常情况下能正确地工作，而在异常情况下也能做出适当处理。

4. 效率

效率（Efficiency）包括运行程序所花费的时间以及运行这个程序所占用的存储空间。算法应该有效使用存储空间，并具有高的时间效率。

通俗地说，效率是指算法的执行时间，对于同一个问题，如果有多个算法可以解决，执行时间短的效率高，存储量需求指算法执行过程中所需要的最大存储空间，效率与低存储量需求这两者都与问题的规模有关，求100个人的平均分与求10000个人的平均分所花的执行时间或运行空间显然有一定差别。

对于规模较大的程序，算法的效率问题是算法设计必须面对的一个关键问题，目标是设计复杂性尽可能低的算法。

5. 简明性

简明性是指算法应该思路清晰、层次分明、容易理解、利于编码和调试，即算法简单、程序结构简单。

简单的算法效率不一定高，要在保证一定效率的前提下力求得到简单的算法。简明性（Simplicity）是算法设计人员努力争取的一个重要特性。

6. 最优性（Optimality）

最优性指求解某类问题中效率最高的算法，即算法的执行时间已达到求解该类问题所需时间的下界。最优性与所求问题自身的复杂程度有关。

例1.3　在n个不同的数中找最大数的算法Find max(L, n)。

输入：数组L，项数n。

输出：L中的最大项max。

max=L[1];  i=2;
while( i<=n )
{   if (max<L[i] )  max=L[i];
    i=i+1;
}

因为max是唯一的，其他的n-1个数必须在比较后被淘汰。一次比较至多可淘汰1个数，所以至少需要n-1次比较。即在有n个数的数组中找数值最大的数，并以比较作为基本运算的算法至少要做n-1次比较。Find max算法是最优算法。

一般来说，正确性和可读性都比效率重要，一个在某些情况下会得出错误结果的算法，即使效率再高，也是没有意义的。当然在基本保证正确的前提下，效率也是非常重要的。

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

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

1. 程序所依赖的算法

求解同一个问题的不同算法，其程序运行时间一般不同。一个好的算法运行时间较少。算法自身的好坏对运行时间的影响是根本的和起作用的。

2. 问题的规模和输入数据

程序的一次运行是针对所求解问题的某一特定实例而言的。因此分析算法性能需要考虑的一个基本问题是所求解问题实例的规模，即输入数据量，必要时也考虑输出的数据量。此外问题的规模必须考虑数据的数值大小；再有需要说明的是即使是在同一计算机系统运行同一个程序，问题实例的规模也相同，由于输入数据的状态（如排列次序）不同，所需的时间和开销也会不同。

3. 计算机系统的性能

算法运行所需要的时间还依赖于计算机的硬件系统和软件系统。

1.3.3 算法复杂度

算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂程度体现在运行该算法所需要的计算机资源的量上。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。而计算机的资源最重要的是时间资源和空间（存储器）资源，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性。

算法的复杂度主要包括时间复杂度和空间复杂度。

1. 算法的时间复杂度

算法的时间复杂度指算法运行所需时间，也指执行算法所需要的计算工作量。

（1）度量算法的工作量

一个算法是由基本运算和控制结构（顺序、选择、循环）构成的，则算法执行时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本的运算，以该基本运算重复执行的次数作为算法的工作量。例如：在考虑两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算，而对于所用的加法（或减法）运算可以忽略不计。

算法所执行的基本运算次数还与问题的规模有关。例如，两个20阶矩阵相乘与两个3阶矩阵相乘所需要的基本运算（即两个实数的乘法）次数显然是不同的。前者需要更多的运算次数，因此，在分析算法的工作量时，还必须对问题的规模进行度量。

综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。即算法的工作量=f (n)，n是问题的规模。

例如，两个n阶矩阵相乘所需要的基本运算（即两个实数的乘法）次数为n3，即计算工作量为n3，也就是时间复杂度为n3。

（2）算法的执行时间绝大部分花在循环和递归上

对于循环语句的时间代价一般用以下三条原则分析：

① 对于一个循环，循环次数乘以每次执行简单语句的数目即为其时间代价。

② 对于多个并列循环，可先计算每个循环的时间代价，然后按加法规则计算总代价。

③ 对于多层嵌套循环，一般可按乘法规则计算。但如果嵌套是有条件的，为精确计算其时间代价，要仔细累加循环中简单语句的实际执行数目，以确定其时间代价。

对于递归算法，一般可把时间代价表示为一个递归方程。解这种递归方程最常用的方法是进行递归扩展，通过层层递归，直到递归出口，然后再进行化简。

下面给出一类递归方程的求解方法。设递归方程为

递归扩展过程如下：

（3）时间复杂度（Time Complexity）

为了避免考虑计算机系统的性能对算法分析的影响，假定算法（程序）在一台抽象的计算机模型上运行。

设抽象机提供m个基本运算（也可称为语句）组成的运算集O={O1,O2,…,Om}，每个运算都是基本的，他们的执行时间是有限常量。同时，设执行第i个运算Oi所需的时间是αi，1≤i≤m。因此一个算法对于给定输入在抽象机上的一次运行过程，表现为执行一个基本运算的序列。

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

（4）最好、最坏和平均时间复杂度

在具体分析一个算法的工作量时，还会存在这样的问题：对于一个固定的规模算法所执行的基本运算次数是否相同呢？下面我们举例进行说明。

例1.4　在长度为n的一维数组中查找值为x的元素。

若采用顺序搜索法，即从数组的第一个元素开始，逐个与被查值x进行比较，显然，如果第一个元素恰为x，则只需要比较1次，但如果x为数组的最后一个元素，或者x不在数组中，则需要比较n次才能得到结果。因此，在这个问题的算法中，其基本运算（比较）的次数与具体被查值x有关。

因此，在算法规模n相同，但输入的数据I不同，算法所需的时间开销也会不同。如果算法执行所需的基本运算的次数取决于某一特定输入，这样就存在最好B(n)、最坏W(n)和平均A(n)情况。

最坏情况指在规模为n时，算法所执行的基本运算的最大次数。平均情况指用各种特定输入下的基本运算次数的数学期望值来度量算法的工作量。

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

这三种时间复杂度从不同角度反映算法的效率，但各有局限性。在很多情况下，各种输入数据集出现的概率很难确定，算法的平均复杂度也就难以确定，其中比较容易分析和计算，且也最具有实际价值的是最坏情况时间复杂度。W(n)的计算比A(n)方便得多，由于W(n)实际上是给出了算法工作量的上界，因此它比A(n)更具有实用价值。因此本书算法分析的重点集中在最坏情况时间复杂度的分析和计算上。

下面通过一个例子来说明算法复杂度的平均情况分析和最坏情况分析。

例1.5　在例1.4中采用顺序搜索法，在长度为n的一维数组中查找值为x的元素，即从数组的第一个元素开始，逐个与被查值x进行比较，基本运算为x与数组元素比较。

首先考虑平均性态分析，设被查项x在数组中出现的概率为q，则ti=i（1≤i≤n，当x为数组中第i个元素时，则需要比较i次），或ti=n（i=n+1，当x不在数组中时，需要和数组中所有元素比较）。

如果假设x出现在数组中每个位置的可能性是一样的，则x出现在每一个位置的概率为q/n，而x不在数组中的概率为1-q。则pi=q/n（当1≤i≤n时），或pi=1-q（当i=n+1时）。

如果x一定在数组中q=1，A(n)=(n+1)/2，这就是说，顺序搜索法查找时，平均情况下需检查数组的一半元素。

再考虑最坏情况分析，最坏情况就是x在数组的最后一个元素或x不在数组中的时候。

W(n)=max{ti|1≤i≤n+1}=n

还有一种类型的时间效率称为分摊效率，它并不针对算法的单次运行，而是计算算法在同一数据结构上执行一系列运算的平均时间。

2. 算法的空间复杂度（Space Complexity）

算法的空间复杂度是指算法运行所需的存储空间。

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的空间以及算法执行过程中所需要的额外空间，分为以下两部分。

（1）固定空间需求（Fixed Space Requirement）

固定空间与所处理数据的大小和个数无关。即与问题实例的特征无关，主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。

（2）可变空间需求（Variable Space Requirement）

可变空间与算法在某次运行中所处理的特定数据的规模有关。这部分存储空间包括数据元素所占的空间，以及算法执行所需的额外空间。

若输入数据所占空间只取决于问题本身和算法无关，则只需要分析除输入和程序之外的额外空间，否则应同时考虑输入本身所需空间。若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。

根据算法执行过程中对存储空间的使用方式，我们又把对算法空间代价的分析分成两种情形：静态分析和动态分析。

① 静态分析

一个算法静态使用的存储空间，是指在算法执行前，可以通过对程序静态的分析确定的使用空间，称为静态空间。

在静态空间分析中，值得注意的是数组（静态数组），它占用了大部分静态空间。

② 动态分析

一个算法在执行过程中以动态方式使用的存储空间是指在算法执行过程中动态分配的存储空间，它们从程序的表面形式上不能完全确定，我们把在算法执行过程中才能确定的空间称为动态空间。动态空间的确定主要由两种情况构成：一是函数的递归；二是调用动态分配（Malloc）和回收（Free）函数。

应当注意的是，空间复杂度一般按最坏情况来分析。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。

1.3.4 使用程序步分析算法

1. 度量一个程序的执行时间通常有两种方法

（1）事后统计的方法

因为很多计算机内部都有计时功能，有的甚至可精确到毫秒级，不同算法的程序可通过运行程序时测试该程序在所选择的输入数据下实际运行所用的时间，以分辨不同算法的优劣。

通过一个算法在给定输入下所执行的总的语句条数来计算算法的时间复杂度，有两个缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣，因此人们常采用另一种事前分析估算的方法。

（2）事前分析估算的方法

一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于以下几个因素。

① 选用了怎样的算法。

② 问题的规模。例如，求100以内还是10000以内的素数。

③ 书写程序的语言。对于同一个算法实现语言的级别越高，执行效率就越低。

④ 编译程序所产生的机器代码的质量。

⑤ 机器执行指令的速度。

显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。

在不考虑计算机系统因素的影响下，对算法自身的特性进行事前分析，即在算法实际运行前分析算法的效率，这种分析结果显然不可能是程序运行时间的具体值，而是运行时间的一种事前估计。

2. 使用程序步分析算法

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

程序步的概念可以进一步简化算法的分析，它并不是直接计算总的语句执行条数，而是将若干条语句合并成一个程序步来计算。

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

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;
}

程序步为：2n+3

引入程序步的目的是为了简化算法的事前分析，不同的程序步在计算机上的实际执行时间通常是不同的，程序步并不能确切反映程序运行的实际时间。而且一个程序在一次运行中的总程序步的精确计算往往也是困难的。

1.3.5 渐近表示法

在分析解决同一个问题的两个算法中，如果一个算法比另外一个算法多一个步骤，我们会认为这两个算法的效率没有什么不同，如果多10个、100个步骤，这两个算法的效率是否有区别？问题的核心就是我们需要有一个衡量标准，在此标准内的算法的效率被认为是差不多的，而超过这个范围，效率就有很大的不同，所以我们需要讨论对数量级的表述。

考虑算法在输入规模趋向无穷时的效率分析就是所谓的渐近分析。在忽略具体机器、编程或编译器的影响下，只考察输入规模n趋向无穷时算法效率的表现，即我们关注的是趋势。

一般来说，当N单调增加且趋于∞时，T(N)也将单调增趋于∞。对于T(N)，如果存在函数T′(N)，使得当N→∞时有(T(N)-T′(N))/T(N)→0，那么我们就说T′(N)是T(N)当N→∞时的渐近性态。在数学上，T′(N)是T(N)当N→∞时的渐进表达式。例如，3N2+4Nlog2N+7与3N2。

渐近表示大大降低了分析算法的难度，免除精确计数的负担，从而是算法分析的任务变得可以控制。下面引入各种具体的渐近表示，使得有望使用程序步在数量级上估计一个算法的执行时间，从而实现算法的事前分析。

1. 运行时间的上界（大O记号）

设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正整数n0和正常数c，使得当n≥n0时，有f(n)≤cg(n)，就称f(n)的阶至多是O(g(n))，记作f(n) = O(g(n))，称为大O记号（Big Oh Notation），如图1-3所示。

这个定义的意义是：当n充分大时有上界，且g(n)是它的一个上界，即f(n)的增长至多像g(n)那样快。它用以表示一个算法运行时间的上界。对于给定的f可有无数个g与之对应，在算法分析中，应当选择最小的函数g作为f的上界。

例1.6　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时，程序1-4的不会超过3n，2n+3=O(n)。

例1.7　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)。

例1.8　f(n) = 2n2+3，g(n)=n2。

当n≥3时，2n2+3≤3n2，所以，可选c=3，n0 = 3。对于n≥n0，f(n)= 2n2+3≤3n2，所以f(n) = O(n2)，即2n2+3=O(n2)。

例1.9　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)。

例1.10　10n2 + 9≠O(n)。

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

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

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

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

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

使用大O记号及下面定义的几种渐近表示法表示的算法时间复杂度，称为算法的渐近时间复杂度（Asymptotic Complexity），简称时间复杂度。

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

【程序1-5】矩阵乘法

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
    }

2. 运行时间的下界（Ω记号）

设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正整数n0和正常数c，使得当n≥n0时，有f(n)≥cg(n)，就称f(n)的阶至少是的Ω(g(n))，记作f(n) =Ω(g(n))，称为Ω称记号（Omega Notation），如图1-4所示。

这个定义的意义是：当n充分大时有下界，且g(n)是它的一个下界，f(n)的增长至少像g(n)那样快。它用以表示一个算法运行时间的下界。

例1.11　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)。

例1.12　f(n)=2n2+3，g(n)=n2。

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

例1.13　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)。

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

3. 运行时间的准确界（Θ记号）

设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正整数n0和正常数c1和c2（c1≤c2），使得当n≥n0时，有c1g(n)≤f(n)≤c2g(n)，就称f(n)的阶是Θ(g(n))，则记作f(n)=Θ(g(n))，称为Θ记号（Theta Notation），如图1-5所示。

即f(n)=Θ(g(n))当且仅当f(n)=O(g(n))且f(n)=Ω(g(n))，此时称f(n)与g(n)同阶。这个定义的意义是：f(n)的增长像g(n)一样快。

例1.14　f(n) = 2n+3 = Θ(n)，即2n + 3= Θ(n)。

例1.15　f(n) = 2n2+3，g(n)=n2。则可以取n0 =3，c1 =1，c2 =3。

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

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

4. 算法按时间复杂度分类

算法按计算时间可分为两类，凡渐近时间复杂度有多项式时间限界的算法称作多项式时间算法（Polynomial Time Algorithm），而渐近时间复杂度为指数函数限界的算法称作指数时间算法（Exponential Time Algorithm）。

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

O(1)<O(log2 n)<O(n)<O(nlog2 n)<O(n2)<O(n3)

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

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

随着n的增大，算法在所需时间上非常悬殊，如图1-6所示。