计算机算法的时间复杂度分析

1.2.4　计算机算法的时间复杂度分析

算法所需执行时间通常随其所处理问题规模n的增大而递增。一般说来，它总为n的函数。

定义1.3　设问题规模为n，算法A处理该问题所需执行时间为函数T（n），则称T（n）为算法A的渐近时间复杂度（Asymptotic Time Complexity），简称时间复杂度。

一、时间复杂度计算

算法的时间复杂度函数T（n）可通过计算一个算法的执行时间来获得。任一操作的执行时间，为该操作执行一次所需时间与执行次数的乘积；一个算法的执行时间，等于其所有操作执行时间的总和。因此，算法执行时间T（n）的计算公式，可定义如下（1≤i≤n）：

显然，算法的执行时间与操作执行次数之和，呈现极大正相关（有时，可视为成正比）。这表明，要想精确计算各种操作执行完一遍所需时间极为困难，甚至不可能（因为同一个算法的不同输入，往往产生不同的运算次数，而一个算法的所有不同输入的数量级可能十分庞大，更何况还与它对应的程序执行时的硬件环境、编程语言、编译程序的性能质量及运行环境等因素均有关）。

事实上，在算法分析中，人们往往只需知道时间耗费的增长率大体在什么范围内，并可用粗略估计而得的算法中操作执行最大次数来作为算法时间效率的度量。因此，算法的具体执行时间或者平均运算次数，若非十分必要，则尽可不必精确计算，而通常只需估算即可。

二、时间复杂度估算

算法时间复杂度的估算，需要了解其分析法与算法阶。

1．时间复杂度的事后分析法

算法时间复杂度的事后分析法，是先将算法用程序设计语言实现，然后再测量性估算所得程序的运行时间。它的缺点是：

（1）必须先把算法转换为其对应程序，并上机运行该程序，才能用所测算的程序执行时间差来间接进行算法时间复杂度分析，故它有违算法分析所要求的直接对算法进行其时间复杂度分析。

（2）同一算法对应的不同程序，在相同环境下其运行时间的测算分析结果可能不同，故其结果一致性差、工作效率太低。

（3）同一算法对应的同一程序，若其运行环境（如硬件、软件环境）以及其他因素的不同，可能导致或掩盖算法本身的真实时间复杂度。

因此，一般很少采用事后分析法对算法进行时间复杂度分析，除非是一些特别精密的控制算法或非常不易分析的复杂算法。

2．时间复杂度的事前估算法

一般说来，一个特定算法的“执行时间”的工作量大小只依赖于问题规模（通常用整数n表示）而定，即算法的时间效率T是问题规模n的正函数T（n）。

算法时间复杂度的事前分析法，不考虑算法的编程实现，而是直接对算法执行时间函数T（n）进行数学性估算，因而，它可克服算法时间复杂度事后分析法的缺点。

3．算法复杂阶

为了更好地分析算法的时间复杂度与空间复杂度，应引入算法复杂阶。

定义1.4　若记算法规模为非负整数n，其算法执行时间为正函数T（n），算法存储空间为正函数S（n）；则随着问题规模n的增长：

（1）算法执行时间T（n）增长率阶的差异性质，称为算法时间复杂阶。

（2）算法存储空间S（n）增长率阶的差异性质，称为算法空间复杂阶。

（3）算法时间复杂阶与算法空间复杂阶，合称算法复杂阶。

定义1.5　记算法A的规模为非负整数n，算法A的时间复杂度为正函数T（n），而f（n）、g（n）为正函数。随着问题规模n的增长：

（1）如果存在正常数c和n₀，使得当n≥n₀时，恒有T（n）≤c⋅f（n），则称当n充分大时f（n）为T（n）的上界增长率函数，记为T（n）=O（f（n））。

（2）如果存在正常数c和n₀，使得当n≥n₀时，恒有T（n）≥c⋅g（n），则称当n充分大时f（n）为T（n）的下界增长率函数，记为T（n）=Ω（g（n））。

（3）如果存在正常数c₁、c₂和n₀，使得当n≥n₀时，恒有c₁⋅f（n）≤T（n）≤c₂⋅f（n），则称当n充分大时T（n）与f（n）的增长率相同（或称同阶），记为T（n）=Θ（f（n））。

定义1.5表明：

（1）算法A的时间复杂度T（n），至多为其上界函数f（n）的某常数倍，至少为其下界函数g（n）的某常数倍；

（2）若O（f（n））=T（n）=Ω（g（n）），则T（n）=Θ（f（n））。

定义1.6　若对于任给定正数e ＆gt; 0，存在非负整数n₀，当n≥n₀时，恒有f（n）≤e⋅g（n），则称当n充分大时函数f（n）的阶比g（n）低，记为f（n）=o（g（n））。

定义1.7　若g（n）=o（f（n）），即当n充分大时f（n）的阶比g（n）高，则记f（n）= ω（g（n））。

定义1.8　算法时间复杂度分析，是具体确定某算法的执行时间T（n）的增长率与何种形式函数f（n）的增长率之间有什么性质的算法时间复杂阶关系。

例如：如果存在某一正常数c，使一个算法在时间c⋅n²内能处理问题规模为n的问题，则此算法的时间复杂度T（n）是O（n²）。

定理1.1　同阶函数中的低阶项，并不影响其算法复杂阶的阶数。

定理1.1说明：两个同阶函数，可以相差一个常数因子，还可以相差比阶低的任何项。事实上，在算法复杂度实际分析中，一般都可只取一个简单形式函数（如log n，n，n²，n³，n⁶等）作为算法复杂阶的阶数之规范表示。不过，若要进一步分析T（n），就应充分考虑低阶项和常数因子对T（n）的影响。

复杂度的上界（即执行算法的各个步骤所需资源之和的最大值up（n））和下界（即执行算法的各个步骤所需资源之和的最小值1ow（n）），是用以估计问题所需某资源（时间资源或空间资源）的复杂程度的界限函数。复杂度上界的阶越低，则算法评估就越精确，分析结果就越有价值；而知道问题的复杂度下界，可帮助人们找到或确认最优算法。例如，如果解决某问题的每一算法，其占用资源的复杂度总小于up（n），则up（n）必是该问题复杂度的一个上界；如果对解某问题的任一算法，其复杂度都大于1ow（n），则1ow（n）定是该问题复杂度的一个下界。显然，确立下界比确定上界要困难得多。

4．复杂阶的等级类型

算法时间复杂度的复杂阶，通常有如下等级类型：

（1）时间复杂度表达式为“c”（c ＆gt; 0）的算法，称为常数时间算法（constant-time algorithm）。例如：T（n）=1，T（n）=3，T（n）=7；均为O（1）。

（2）时间复杂度表达式为“an+b”（a ＆gt; 0，b≥0）的算法，称为线性时间算法（Linear-line algorithm）。例如：T（n）=3n+8，T（n）=7n；均为O（n）。

（3）时间复杂度表达式为“an²+bn+c”（a ＆gt; 0，b≥0，c≥0）的算法，称为平方时间算法（Quadratic-time algorithm）。例如：下列各种平方时间均为O（n²），它们还可再细分为：

① 纯粹平方时间（Pure Quadratic-time）——其时间复杂度表达式为an²+c，其中a＆gt;0，c≥0。例如：T（n）=6n²+4，T（n）=7n²+9，T（n）=n²+6。

② 完全平方时间（Complete Quadratic-time）——其时间复杂度表达式为an²+bn+c，其中a＆gt;0，b＆gt;0，c≥0。例如：T（n）=n²+4n+4，T（n）=7n²+n+9，T（n）=n²+n+6。

（4）立方时间（Cubic-time）——其时间复杂度表达式为an³+ bn²+cn+d，其中a＆gt;0，b≥0，c≥0，d≥0。例如：T（n）=n³，T（n）=n³+5n²+2n+8，均为O（n³）。

图1.1　算法时间复杂度常见表达式差异程度示意图

（5）对数时间（logarithm-time）——其时间复杂度表达式为log n。例如：T（n）=log n，T（n）=3+log n，均为O（log n）。

（6）复合对数时间（Combined-logarithm-time）——其时间复杂度表达式为n log n。例如：T（n）=n log n，T（n）=23+n log n，均为O（n log n）。

（7）指数时间（exponential-time）——其时间复杂度表达式为2ⁿ。例如：T（n）=2ⁿ，T（n）=n+2ⁿ，均为O（2ⁿ）。

显然，对自然数c和n，当n足够大时，如图1.1所示，各式满足：

c ＜ log n ＜ n ＜ n log n ＜ n² ＜ n³ ＜ 2ⁿ ＜ n! ＜ nⁿ

最常见的时间复杂度表达式为常数时间c、对数时间log n、线性时间n、复合对数时间n log n、平方时间n²、立方时间n³、指数时间2ⁿ、阶乘时间n!、自幂（指其底数、指数均为自身）时间nⁿ的算法，其时间复杂度表达式的大小关系为：

O（1）＜O（log n）＜O（n）＜O（n log n）＜O（n²）＜O（n³）＜O（2ⁿ）＜O（n!）＜O（n n）

三、算法时间复杂度的最好、最坏和平均情况

关于某类问题的复杂度上、下界的研究，属于计算复杂性理论研究范围，本书不予深入讨论。在此，仅针对某一具体算法进行算法分析。在分析有选择控制结构的算法，特别是基本操作在选择控制结构之中时，很难笼统地估算算法的时间复杂度。这时，就要确定能反映出算法在各种情况下工作的数据集，选取的数据就要能够反映和代表各种计算情况下的估算，包括最好情况下的时间复杂度（即时间复杂度下界，记为T_min）、最坏情况下的时间复杂度（时间复杂度上界，记为T_max）、平均情况下的时间复杂度（平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下的算法的期望运行时间，也就是执行各个步骤所需时间之和的平均值，记为T_avg）和有代表性的其他情况；并且，要通过合理配置使用这些典型数据样例来进行算法分析。

定义1.9　设某一领域问题的输入的规模为n，D_n是该领域问题的所有输入集合，任一输入I∈D_n，P（I）是I出现的频率，∑_P（I）=1，T（I）是（解决该领域问题的）算法在输入I 下所执行的基本运算次数；则可定义该算法的：

（1）最好时间复杂性为　T_min（n）=min{T（I）}；

（2）最坏时间复杂性为 T_max（n）=max{T（I）}；

（3）平均时间复杂度为　T_avg（n）=∑_{P（I）T（I）}。

这三种情况下的时间复杂度，从不同视角反映了算法效率状况，故各有其用，也各有其局限。实践表明，最坏情况下的时间复杂度，其可操作性最好，且最有实际价值。因此，最坏情况分析往往是时间复杂度分析重点。

一般来说，最好情况、最坏情况的时间复杂度是很难计量的，原因是对于问题的任意确定的规模n是否达到了T_min（n）、T_max（n）的合法输入难以预料或确定，而规模n的每一个输入的概率也难以预测或确定。为此，有时也按平均情况来计量时间复杂度，但它又要对输入不同数据的概率先做出人为假设（一般假定为等概率）后方能进行，若缺乏必要根据，则所做假设未必符合实际。

应当指出，不时耳闻“现代计算机的运算速度越来越快，研究精良算法已经没有必要”，然而，这完全是一种误解或者偏见。

如表1.1所示，时间复杂度函数不同的数算法A₁～算法A₅，其时间复杂度函数近似值随其问题规模n而快速增长。表1.1说明，算法时间复杂度函数为n²、n³、2ⁿ时，时间复杂度将随问题规模增大变得极为巨大，使解决问题的时间严重失控（使人不可容忍）！

表1.1　不同时间复杂度函数随问题规模n而快速增长的对比

又如表1.2所示，时间复杂度函数不同的数算法A₁～算法A₅，其提高时间复杂度远比提高计算机速度更为经济。在表1.2中，设算法A₁在1秒内可处理问题规模为106个数据输入；记SB_i为算法i的原最大可处理问题规模，SA_i为电脑速度提高10倍后的算法i最大可处理问题规模。对算法时间复杂度较高的算法A₄，若改用复杂度较低的A₃、A₂代替，则分别可解比原问题规模大3 987 061倍的同一问题。由此可见，算法改进所提升的软件效果，远远大于电脑速度提高的硬件效果。

表1.2　提高时间复杂度远比提高计算机速度更经济的比较

四、算法的空间复杂度分析

算法的空间复杂度与时间复杂度共同构成算法复杂度。

定义1.10　设问题规模为n，则算法执行过程中所占用存储空间大小称为算法的空间复杂度，记为S（n）=O（f（n））。

算法所需存储空间，包括算法程序所占的空间、输入数据所占的存储空间以及算法执行过程中所需要的辅助空间（如程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间等）。若输入数据只取决于问题本身，与算法无关，则只需要分析除输入和程序之外的额外空间。在许多实际问题中，常采用压缩技术，以尽量减少不必要的额外空间开销。

鉴于算法的空间复杂度分析颇类似算法的时间复杂度分析，而空间复杂度分析可参照时间复杂度分析来施行，故可从略。

此外，顺便指出，在计算复杂性理论中，存在以下问题类。

（1）具有多项式时间复杂性的简单问题类，称为多项式问题类，简记为P。人们公认，多项式时间问题类是易解问题，故具有多项式时间复杂度的算法被视为好的算法。

（2）许多复杂问题，其已知的最好算法也具有指数时间复杂度，且人们并不知道这些问题是否存在多项式时间算法；故称这些具有非多项式时间复杂度的复杂问题类为非多项式问题类，简记为NP。

（3）现实（如组合学、图论、运筹学等领域）中往往存在大量高复杂度的同质类问题，其计算复杂性是同构的（即它们的时间复杂度具有本质等效性），倘能用多项式时间解决它们当中的一个问题，则它们全都能用多项式时间求解，故称此种问题类为NP完全问题类。值得注意的是，NP完全问题类的研究，至今仍是计算复杂性理论研究的难点与重点之一。