1.4.2 时间复杂性

1．时间复杂性的表示

算法的时间复杂性是指算法运行所需的时间资源的量，从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要求解的问题的规模（N）、算法的输入（I）和算法本身（A）的函数。比如，例1-2的迷宫问题中，棋盘的大小N反映了迷宫问题的求解规模，某个特定的棋盘布局则表示了迷宫问题的输入。显然，用某个特定算法A求解该问题时，求解图1-1(a)所示问题实例和图1-1(b)所示问题实例所需的时间不一样。一般地，问题规模N越大，所需要的时间就越多。即使在问题规模N相同的情况下，求解不同输入所对应的问题实例所需要的时间也不一样。比如，应用普通广度优先搜索算法求解图1-1(b)和图1-1(c)所需要的时间也不尽相同。

不失一般性，如果分别用N、I和A表示算法要求解问题的规模、算法的输入和算法本身，用T表示算法的时间复杂性，那么

其中，T(N,I,A)是N、I和A的一个确定的三元函数。通常，人们让A隐含在复杂性函数名当中，于是式(1-1)可以简写为

运行于特定计算机的算法程序由该计算机系统的若干操作和运算指令组成。显然，运行算法所需要的时间等价于执行这些指令所需要的时间之和。不同的计算机，其指令和执行指令所需要的时间不一定相同，不失一般性，假定算法运行在一台抽象的计算机上，该机提供k种元运算，分别记为O₁,O₂,…,O_k，这些元运算每执行一次所需要的时间分别为t₁,t₂,…,t_k。给定算法A，经过统计，用到元运算O_i的次数为e_i（i=1,2,…,k），显然对于每个i（1≤i≤k），e_i是N和I的函数，即e_i=e_i(N,I)。那么，算法执行时间的表达式为

其中，t₁,t₂,…,t_k是与N和I无关的常量。

对于任何一个问题，特定规模N的问题实例通常比较多，甚至大得无法计量。比如，迷宫问题的规模N=1000时，其对应的问题实例有21000×1000个。显然，不可能对规模N的每种合法输入I都统计e_i(N,I)（i=1,2,…,k）。因此T(N,I)的表达式还需简化，或者说，只在规模为N的某些或某类有代表性的合法输入中统计相应的e_i(N,I)（i=1,2,…,k），才能评价其时间复杂性。

下面只考虑三种情况的时间复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为T_max(N)、T_min(N)和T_avg(N)。在数学上有

其中，D_N是规模为N的合法输入的集合；I*是D_N中一个使T(N,I*)达到T_max(N)的合法输入；是D_N中一个使T(N,)达到T_min(N)的合法输入；而P(I)是在规模为N的问题实例集合中出现输入I的概率。

以上三种情况下的时间复杂性各从某个角度反映了算法的效率，各有各的用处，也各有各的局限性。实践表明，可操作性最好的、最有实际价值的是最坏情况下的时间复杂性。最好情况和平均情况下的时间复杂性分析一般应用于理论研究。本书对算法时间复杂性的分析主要放在最坏情形上。

2．渐进时间复杂性及其阶

虽然式(1-4)严格定义了算法在最坏情况下的时间复杂性，但是在问题求解过程中，按照式(1-4)去分析和计算算法的时间复杂性是不可行的。

首先，随着社会的进步、科学研究的深入，要求用计算机解决的问题越来越复杂，规模越来越大，导致严格定义的最坏情况的时间复杂性T_max(N)形式会非常复杂。

其次，问题的复杂性导致算法和程序结构的复杂性，如果把算法中所有的运算都考虑进去，那么式(1-4)的求解可能会比原问题的求解更困难。本质上，时间复杂性并不是表示一个程序解决某个问题需要花多少时间，而是当问题规模扩大后，程序需要的时间量增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某特定问题实例的效率不能衡量一个程序的好坏，而应该看当这个问题的规模变大若干倍后，程序运行时间是否还是一样，或者增加了若干倍甚至更多倍。因此，对于规模充分大、结构十分复杂的问题的求解算法，其复杂性分析需要进行合理的简化。

首先，引入复杂性渐近态的概念。设T(N)是前面定义的关于算法A的复杂性函数，一般说来，当N单调增加且趋于∞时，T(N)也将单调增加趋于∞。对于T(N)，如果存在T′(N)，使得当N→∞时有

那么，我们就说T′(N)是T(N)当N→∞时的渐近态，或叫T′(N)为算法A当N→∞时的渐近复杂性。在数学上，T′(N)是T(N)当N→∞时的渐近表达式。而且，T′(N)是T(N)中略去低阶项所留下的主项，所以它无疑比T(N)简单。比如，当T(N)=5N2+6NlogN +3N+N+2时，T′(N)的一个答案是5N2，因为这时

显然，5N2比5N2+6NlogN+3N++2简单得多。

由于当N→∞时T′(N)渐近于T(N)，我们有理由用T′(N)来替代T(N)作为算法A在N→∞时复杂性的度量。而且，由于T′(N)比T(N)简单，这种替代明显是对复杂性分析的一种简化。

进一步，考虑到分析算法复杂性的目的在于比较求解同一问题的两个不同算法的效率，而当要比较的两个算法的渐近复杂性的阶不相同时，只要能确定出各自的阶，就可以判定哪一个算法的效率高。换句话说，这时的渐近复杂性分析只要关心T′(N)的阶就够了，不必关心包含在T′(N)中的常数因子和低阶项。所以，人们常常对T′(N)的分析进一步简化，把计算机中的所有元运算做无差别处理，即假设算法中用到的所有元运算各执行一次，所需要的时间都是一个单位时间。而且，在实际算法复杂性分析时，并不是每个元运算的执行次数都需要统计，往往只需要计算“主要运算”，忽略主运算之外其他运算的开销。

这样，式(1-4)可以简化为

其中，e_p是算法的“主要运算”，I*是输入实例集合中一个使T(N,I*)达到T_max(N)的合法输入。

通过上面的两个步骤，算法复杂性分析得到了极大的简化。实际上，算法复杂性分析只要考察当问题的规模充分大时，算法复杂性在渐进意义下的阶。与此简化的复杂性分析相配套，需要引入以下渐进意义下的记号：O，Ω，Θ。

以下设f(N)和g(N)是定义在正数集上的正函数。

（1）渐进符号O的定义

如果存在正的常数C和自然数N₀， 使得当N≥N₀时有f(N)≤Cg(N)，则称函数f(N)当N充分大时有上界，且g(N)是它的一个上界，记为f(N)=O(g(N))，或者说f(N)的阶不高于g(N)的阶。例如：

① 存在C=5，N₀=1，对所有N≥N₀有4N≤CN，则4N=O(N)。

② 存在C=14，N₀=1，对所有N≥N₀有2N+12≤CN，则2N+12=O(N)。

③存在C=17，N₀=20，对所有N≥N₀有16N2+19N+5≤CN2，则16N2+19N+5=O(N2)。

④ 存在C=4，N₀=5，对所有N≥N₀有16N2+19N+5≤CN3，则16N2+19N+5 =O(N3)。

⑤ 作为一个反例，N3≠O(N2)。假设等号成立，则存在正的常数C和自然数N₀，使得当N≥N₀时有N3≤CN2，即N≤C。显然，当N=max{N₀,C+1}时，这个式子不成立，所以N3≠O(N2)。

除了根据符号O的定义来计算一个函数的O表达式，大O比率定理提供了另一种判定规则。

【大 O 比率定理】 对于函数f(N)和g(N)，如果极限存在，则f(N)=O(g(N))当且仅当存在正的常数C，使得≤C。

证明：略。

例子：

① 因为，所以3n+2=O（n）。

② 因为，所以10n2+4n+2=O(n2)。

③ 因为，所以6×2n+n2=O(2n)。

④ 因为，所以n16+3×n2=O(2n)。

符号O是为了简化算法复杂性分析而采用的一种记号，有两点需要特别注意：

① 符号O定义的是一个算法当其问题规模充分大时算法复杂性的一个上界。根据符号O的定义不难推导，这个上界并不是唯一的。比如，在（1）中的例子③和例子④中，N2和N3都是16N2+19N+5符合O定义的上界。显然，这个上界的阶越低，则越接近算法复杂性的真实值，评估就越精确，结果就越有价值。

②f(N)=O(g(N))不一定能推导出g(N)=O(f(N))，因为两者并不等价。实际上，这里的等号并不是通常相等的含义。

按照符号O的定义，容易证明它有如下运算规则：

下面按照符号O的定义，证明第一条运算规则。

设F(N)=O(f)，根据符号O的定义，存在正常数C₁和自然数N₁，使得对所有的N≥N₁，有F(N)≤C₁f(N)。

类似地，设G(N)=O(g)，则存在正的常数C₂和自然数N₂，使得对所有的N≥N₂有G(N)≤C₂g(N)。

令C₃=max(C₁,C₂)，N₃=max(N₁, N₂)，对于任意自然数N≥N₃，有

其余规则的证明类似，请读者自行证明。

（2）渐进符号Ω的定义

如果存在正的常数C和自然数N₀，使得当N≥N₀时有f(N)≥Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))，或者说f(N)的阶不低于g(N)的阶。

类似符号O，符号Ω也存在如下判定规则。

【大Ω比率定理】 对于函数f(N)和g(N)，如果极限存在，则f(N)=Ω(g(N))当且仅当存在正的常数C，使得≤C。

证明：略。

同样，用Ω评估算法的复杂性得到的只是该复杂性的一个下界。这个下界的阶越高，则评估就越精确，结果就越有价值。这里的Ω只对问题的一个算法而言。如果它是对一个问题的所有算法或某类算法而言，即对于一个问题和任意给定的充分大的规模N，下界在该问题的所有算法或某类算法的复杂性中取值，那么它将更有意义。这时得到的相应下界被称为问题的下界或某类算法的下界。它常常与O配合，以证明某问题的一个特定算法是该问题的最优算法，或者该问题在某算法类中的最优算法。

（3）渐进符号Θ的定义

f(N)=Θ(g(N))当且仅当f(N)=O(g(N))且f(N)=Ω(g(N))，这时称f(N)与g(N)同阶。

同时，f(N)=Θ(g(N))等价于存在正的常数c₁、c₂和N₀，使得对于所有的N≥N₀，有c₁(g(N))≤f(N)≤c₂(g(N))。即函数f介于函数g的c₁和c₂倍之间，当N充分大时，g既是f的下界，又是f的上界。同样，符号Θ也存在如下判定定理。

【大Θ比率定理】对于函数f（N）和g（N），如果极限与g（N))都存在，则f（N）=Θ（g（N))当且仅当存在正的常数c₁，c₂，使得≤c₁,≤c₂。

比较大O比率定理和大Ω比率定理可知，大Θ比率定理实际是那两种情况的综合。对于多项式情形的复杂性函数，其阶函数可取该多项式的最高项，即有如下定理。

【定理 1-1】 对于多项式函数f(N)=a_mNm+a_m−1Nm−1+…+a₁N+a₀，若a_m>0，则

3．时间复杂性渐进阶的意义

计算机的设计和制造技术在突飞猛进，一代又一代计算机的计算速度和存储容量在直线增长。有人因此认为没有必要去追求高效率的算法，从而不必无谓地进行复杂性的分析；低效的算法可以由高速的计算机弥补，在可接受的时间内用低效的算法完不成的任务，只要移植到高速的计算机上就能完成。这是一种错觉！造成这种错觉的原因是他们没看到：随着经济的发展、社会的进步、科学研究的深入，计算机求解的问题越来越复杂、数据规模越来越大。对低效算法来说，问题复杂程度和规模的线性增长导致的时耗的增长和空间的增长都会是超线性的。下面对效率上有代表性的几个档次的算法进行简单对比。

假设求解某一个问题有5个不同算法，其时间复杂性分别为N、N2、N3、2N、3N，这5个算法在同一台计算机上运行，并且求解不同规模的问题实例（假定运行实例都是在该问题规模下需要时间最多的问题实例）。这5个不同阶时间复杂性的算法在该台计算机上求解不同规模问题实例所需时间如表1-1所示。从表1-1可以看出，对于复杂性阶为N的算法，当问题实例规模扩大6倍时，它所需时间也只增长了6倍，是一个线性增长的过程；但是对于复杂性阶为3N的算法，当问题实例规模扩大6倍时，其所需时间的增长速度是一个指数增长过程，它所需的时间高达1.3×1013世纪，这是一个几乎不可能完成的计算任务。总之，对于低效的算法（指数级复杂性算法），虽然它能求解规模比较小的问题实例，但是当求解的问题实例规模扩大若干倍时，它求解该问题实例所需的时间会爆炸式地增长，在现实意义上其求解过程变得不可能。

同样，假设求解某一个问题有 5 个不同算法，其时间复杂性阶分别为N、N2、N3、2N、3N，这5个算法在不同运算性能的计算机上运行。它们在不同运行速度的计算机上能求解的问题实例规模如表1-2所示。从表1-2可以看出，对于复杂性阶为N的算法，在1倍速计算机上能求解最大规模为N₁的问题实例，在运行速度提高1000倍的计算机上能求解的问题实例最大规模为1000N₁，是一个线性增长的过程；但是对于复杂性阶为3N的算法，在1倍速计算机上能求解最大规模为N₅的问题实例，在运行速度提高1000倍的计算机上能求解的问题实例最大规模并没有增长1000倍，相反，它能求解的问题实例最大规模仅仅增加了6.29（几乎微不足道）。总之，对于低效的算法（如指数级复杂性算法），计算机的计算速度成倍乃至数千倍地增长基本上不会带来求解规模的较大增益。因此对于低效算法，问题求解规模的增大不能寄希望于移植算法到高速的计算机上，而应该把着眼点放在算法的改进上。

从表1-1和表1-2可以看出，限制求解问题规模的关键因素是算法渐近复杂性的阶。对于表中的前三种算法，其渐近时间复杂性与规模N的幂同阶。相应地，求解问题规模的增大带来所需时间倍数增长，增长幅度随着幂次的提高而增大。另一方面，计算机计算速度增长带来求解问题规模的倍数增长，只是随着幂次的提高，规模增长的倍数在降低。人们把渐近复杂性与规模N的幂同阶的这类算法称为多项式算法。

对于表中的后两种算法，其渐近的时间复杂性与规模N的一个指数函数同阶。相应地，求解问题规模的线性增大带来的是所需时间的爆炸式增长，计算机计算速度的线性增长只带来求解问题规模的加法增长。人们把渐近复杂性与规模N的指数同阶的这类算法称为指数型算法。

多项式算法和指数型算法在效率上有质的区别。多项式算法是有效的算法，绝大多数问题存在多项式算法。但有些问题还未找到多项式算法，只找到指数型算法。这两类算法的区别本质上是算法渐近复杂性阶的区别。可见，算法渐近复杂性的阶对于算法的效率有着决定性的意义，所以在讨论算法的复杂性时人们基本上只关心它的渐近阶。

在讨论算法复杂性的渐近阶的重要性的同时，有两条要记住：

①“复杂性渐近阶比较低的算法比复杂性渐近阶比较高的算法有效”，这个结论只是在问题的求解规模充分大时才成立。比如，复杂性阶分别为N100和2N的两种算法，前者比后者有效只是在N100<2N即N≥C时才成立，其中C是方程N100=2N的解。当N<C时，后者反而比前者有效。所以对于规模小的问题，不要盲目地选用复杂性阶比较低的算法。其原因包括两方面：首先，复杂性阶比较低的算法在规模小时不一定比复杂性阶比较高的算法更有效；其次，在规模小时，决定工作效率的可能不是算法的复杂性而是代码的效率，哪一种算法简单，实现起来简洁，就选用该算法。

② 当两个算法的渐近复杂性的阶相同时，必须进一步比较渐近复杂性表达式中的常数因子。显然，常数因子小的优于常数因子大的算法。比如，渐近复杂性为NlogN/100的算法显然比渐近复杂性为100NlogN的算法有效。

4．算法时间复杂性分析

如果一个算法中存在递归调用，则被称为递归算法，否则为非递归算法。下面分别讨论非递归算法和递归算法的复杂性分析方法。

（1）非递归算法的复杂性分析

非递归算法一般由串行语句段和循环语句构成，其中循环语句是时间复杂性分析的关键。非递归算法的复杂性分析包括以下三个步骤。

① 确定关键操作。关键操作一般位于循环体内，它可以是赋值、比较、算术运算和逻辑运算等操作（一般被看作基本操作，并约定所用的时间都是一个单位）；另外，关键操作还可以是由多个基本操作构成的程序块。

② 计算关键操作的执行步数T(n)。T(n)一般可以表示为数列和的形式。

③ 求解T(n)渐进阶，并用O记号表示。

应该指出的是：非循环体内的串行程序块执行时间是常数时间；函数调用语句则需要根据该函数的输入规模，按照上述方法分析其时间复杂性，然后把该复杂性与原函数其他部分的复杂性相加，得到整个算法的总复杂性。

程序1-2寻找最大元素如下。

程序1-2中的关键操作是比较运算。for循环中共进行了n−1次比较，所以程序1-2的时间复杂性为O(N)。

在程序1-3中，主要操作是比较和子函数Swap()中的移位操作。因此冒泡排序算法的时间复杂性的评估只要统计Swap()操作的执行次数即可。该操作在最坏情况下的总执行次数为，所以冒泡排序算法的时间复杂性为O(N2)。

（2）递归算法的复杂性分析

过程调用和函数调用语句需要的时间包括两部分，一部分用于实现控制转移，另一部分用于执行过程（或函数）本身。后者可以根据过程（或函数）调用的层次，由里向外运用上述方法进行分析，直到计算出最外层的运行时间。如果过程（或函数）出现直接或间接的递归调用，则上述由里向外逐层分析的方法不再可行。这时需要递归分析的技术。也就是说，先假定递归过程（或函数）所需要的时间为一个待定函数（函数的自变量为递归程序的输入规模），再根据递归调用建立时间复杂性函数的递推方程，最后求解递推方程得到时间复杂性。其复杂性分析过程包括以下三个步骤：

① 分析递归程序的结构，确定每个逻辑块的时间复杂度。非递归的程序块（或者子函数）用非递归方法分析其复杂性，递归函数的复杂性则根据其输入规模递归地表示，这两部分之和则是整个算法的时间复杂性。

② 构造复杂性函数的递归方程。

③ 求解递归方程和渐进阶，并用O记号表示。

递归方程的种类很多，求它们解的渐近阶的方法也很多，这些方法超出了本书的范畴，读者请参阅相关文献。本节以Hanoi塔问题算法为例说明如何建立相应的递归方程，同时不加推导地给出它们在最坏情况下的时间复杂性的渐近阶。

在程序1-4中，算法包括两次Hanoi程序递归调用，且每次递归调用的输入规模为N−1，假定原Hanoi塔问题算法的执行时间为T(N)，则每次递归调用的执行时间为T(N−1)；还包括一次Move函数调用，Move函数的时间复杂性为常数时间，记为c，可以得到如下递归方程，即

T(N)=2T(N−1)+c

求解上述递归方程，可以得到Hanoi塔问题算法的时间复杂性为O(2N)。

在上述算法复杂性分析过程中，我们默认数据已经读入内存，并且所有的运算都在单台计算机执行。但是，在大数据时代，算法可能要处理TB级别规模的数据，显然这些数据无法一次性全部读入内存；另外，算法可能运行在分布式环境中，算法的不同模块在网络中的不同运算节点执行。因此，算法时间复杂性的影响因素除了关键操作的开销，还包括数据读入/导出时文件读写的时间开销，以及分布式环境下数据在网络中传输的时间开销。