2.2 渐进效率分析

在上一节中，详细分析了插入排序算法的运行时间，并定义了算法运行时间增长的阶，它可以简明地说明算法的性能与效率。虽然有时候能够精确的确定某个算法的运行时间，如采用逐条分析插入排序算法代码的方式，但通常来讲没必要如此费力地去计算额外的精确度，对于输入规模足够大的情况来说，在精确表示的运行时间中，常系数和低阶项是由输入规模所决定的，当输入规模增大到使得运行时间的增长只与运行时间的增长量级有关时，此时只需要研究算法的渐进效率，常系数和低阶项都可以忽略不计。本节将介绍几种标准方法来简化算法的渐进分析。

2.2.1 渐进记号

首先给出几种基本的渐进记号和一些常用的扩充用法。

1.Θ记号

Θ记号用于给出一个函数的渐进确界。在上一节中，已经介绍了插入排序算法在最坏情况下的运行时间是T(n)=Θ(n²)。现在就来给出该记号的正式含义。对于一个给定的函数g(n)，用Θ(g(n))来表示一系列函数的集合Θ(g(n))={f(n)}，函数f(n)满足：存在正常数c₁、c₂和n₀，使∀n≥n₀，有0≤c₁g(n)≤f(n)≤c₂g(n)。也就是说，对任意一个函数f(n)，若存在正常数c₁、c₂和n₀，使得当n足够大时，f(n)在c₁g(n)和c₂g(n)中间，则f(n)是Θ(g(n))中的元素，可以写成f(n)∈Θ(g(n))，即g(n)是f(n)的一个渐进确界。

在上一节中，非正式的引入了记号Θ，相当于忽略了最差情况下T(n)中的高阶项的系数以及所有的低阶项。从直观上来看，一个渐进正函数中的低阶项在决定渐进确界时可以被忽略，因为当n很大时，它们就不那么重要了，最高阶项很小的一部分就足以超越所有的低阶项。同样最高阶项的系数也可以忽略，因为它只是将c₁、c₂改变成等于该系数的常数因子。

2.O记号

Θ记号渐进地给出一个函数的上界和下界。当一个函数只有渐进上界时，则使用O记号。给出一个函数g(n)，用O(g(n))表示一个函数集合，即O(g(n))={f(n)}，函数f(n)满足：存在正常数c和n₀，使得对∀n≥n₀，有0≤f(n)≤cg(n)。O记号在一个常数因子内给出某函数的一个上界。用“f(n)=O(g(n))”来表示一个函数f(n)是集合O(g(n))中的一个元素。这里需要注意到f(n)∈Θ(g(n))隐含着f(n)∈O(g(n))，因为Θ记号强于O记号。O记号是用来表示上界的，当用它作为算法的最坏情况运行时间的上界时，就能够确定任意输入的运行时间的上界。因为插入排序在最坏情况下的运行时间的上界O(n²)也适用于每个输入的运行时间，这与等式n=O(n²)成立是一个道理，在本书中，当f(n)∈O(g(n))时，只是说明g(n)的某个常数倍是f(n)的渐进上界，并不反映如何接近该上界。

3.Ω记号

Ω记号被用来给出一个函数的渐进下界。给定一个函数g(n)，用Ω(g(n))表示一个函数集合{f(n)}，其中每个f(n)都满足：

存在正常数c和n₀，使得对∀n≥n₀，有0≤cg(n)≤f(n)。

因为Ω记号描述了渐进下界，当它用来描述一个算法最佳情况运行时间界限时，也隐含给出了在任意输入下运行时间的下界。例如，插入排序算法的最佳情况运行时间是Ω(n)，这隐含着该算法的运行时间是Ω(n)。

根据目前所介绍的三种渐进记号的意义，可以得出以下结论：

定理2.1 对任意两个函数f(n)和g(n)，有f(n)∈Θ(g(n))。当且仅当f(n)∈O(g(n))和f(n)∈Ω(g(n))。

对定理2.1的证明比较简单，本书省略，有兴趣的读者可以自行证明。

目前已经知道插入排序算法的运行时间介于Ω(n)和Ω(n²)之间，因为它处于n的线性函数和二次函数的范围内，进一步讲，这两个界从渐进意义上来说是尽可能精确的，因为插入排序的运行时间不是Ω(n²)，存在一个输入（例如，当输入已经排好序时），使得插入排序的运行时间为Θ(n)。也可以说该算法的最坏情况运行时间为Ω(n²)，两者并不矛盾，因为存在一个输入，使得算法的运行时间为Ω(n²)。一般情况下，当我们说一个算法的运行时间（无修饰语）是Ω(g(n))时，是指对每一个n值，无论取什么规模的输入，该输入的运行时间都至少是一个常数乘以g(n)。

2.2.2 渐进记号的应用

对于渐近性分析，这里只关心函数变化的量级，即函数的最高阶数，而不需要关心它的常数因子及低阶项。渐进分析可以用在对一个算法进行时间复杂度以及空间复杂度的分析中。

1.时间复杂度

时间复杂度被用于度量一个算法执行时间的长短。常见的算法时间复杂度有：常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(n⋅logn)、平方阶O(n²)、立方阶O(n³)……k次方阶O(n^k)和指数阶O(2ⁿ)等。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越来越低。也就是说时间复杂度从小到大依次为：O(1)<O(logn)<O(n)<O(n⋅logn)<O(n²)<O(n³)<…<O(2ⁿ)<O(n!)。

通常情况下，在计算时间复杂度的时候，首先要分析算法中包含的基本操作，然后根据相应的语句结构确定每一个操作的执行次数，再利用上文给出的抽象方法确定T(n)的数量级(1,logn,n,n·logn,n²等)。接下来，令函数f(n)=该数量级，对T(n)/f(n)求极限，若结果为一个常数c，则该算法的时间复杂度为O(f(n))。

那么如何计算一个算法的时间复杂度？通常情况下，有以下几个简单的分析法则：

1）对于简单的说明性语句、输入输出语句、赋值语句，可以近似认为其时间复杂度为O(1)。O(1)代表一个算法的运行时间为常数。

2）对于顺序结构语句块，需要依次执行一系列语句，其时间复杂度遵循O记号下的“求和法则”。所谓“求和法则”指的是：如果算法的两个部分的时间复杂度分别为T1(n)=O(f(n))和T2(n)=O(g(n))，那么可以得到T1(n)+T2(n)=O(max(f(n), g(n)))，特别地，如果T1(m)=O(f(m))，T2(n)=O(g(n))，那么T1(m)+T2(n)=O(f(m)+g(n))。

3）对于选择结构语句块（例如if语句），检验判定条件需要O(1)时间，此外，每一次该语句块只有其中一个分支会被执行，因此它的运行时间是检验判定条件的时间加上执行一个分支语句所用的时间。

4）对于循环结构语句块，循环语句的运行时间主要体现在多次执行循环体以及检验循环条件的时间耗费，其时间复杂度遵循O记号下的“乘法法则”。所谓乘法法则指算法的两个部分时间复杂度分别为T1(n)=O(f(n))和T2(n)=O(g(n))，那么，T1*T2=O(f(n)*g(n))。我们可以将循环体被执行的次数设为T1(n)，将执行一次循环体内语句所需时间看作T2(n)，那么该循环语句块的执行时间为T1*T2。

以上几点规则只是针对一些简单算法或是逻辑结构简单的情况，当算法中采用了复杂的结构或者各种结构嵌套时，单纯使用上述方法显然很难正确地求解算法的时间复杂度，针对这些复杂的情况，最好的方法就是先将它分为几个容易估算的部分，然后再利用求和法则和乘法法则技术计算整个算法的时间复杂度。

2.空间复杂度

读到这里，很多读者可能会有这样一个问题，为什么在衡量算法效率的时候，更多的是关注算法的时间复杂度，而不是算法的空间复杂度，难道空间复杂度就不重要吗？如果不重要，为什么很多时候又特别强调在O(n)或是其他数量级的空间复杂度内解决指定的问题呢？

其实，算法的空间复杂度并非不重要，也并非技术人员不去关注它，只是相较于时间复杂度，技术人员更多地会关注算法的时间性能。空间复杂度的分析方法与时间复杂度的分析方法类似，一个算法的空间复杂度也通常都与该算法的输入规模n有关系，通常也被表示为一个关于n的函数。定义S(n)是一个算法的空间复杂度，通常可以表示为S(n)=O(f(n))或S(n)=Θ(f(n))。其中，n为输入的规模，f(n)表示算法所需的存储空间。

一个程序在执行时，除了需要存储空间来存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的存储单元以及一些为得到计算所需信息的辅助空间。具体而言，程序执行时所需存储空间主要包括以下两部分：固定部分与可变部分。固定部分空间的大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等。这部分属于静态空间。可变部分主要包括动态分配的空间以及递归栈所需的空间。这部分的空间大小与问题规模有关。举一个例子，如果一个算法的空间复杂度为O(1)，那么说明数据规模n和算法所需的辅助空间大小无关，即算法的空间复杂度为一个常量，不随被处理数据量n的大小而改变，并不是说该算法仅仅使用一个辅助空间。当一个算法的空间复杂度与被处理数据量n呈线性比例关系时，可表示为O(n)。

分析一个算法所占用的存储空间要从各方面综合考虑。例如，对于一个算法而言，如果用递归方式实现，那么代码量一般比较简短，几行代码即可实现，但是需要注意的是，虽然算法本身所占用的存储空间较少，然而由于在执行过程中需要多次进行函数调用（调用函数自身），所以在运行时需要一个附加堆栈来记录函数调用的有关信息，从而会产生额外较多的临时存储单元；如果采用非递归的方法实现该算法，那么程序的逻辑关系将会变得较为复杂，代码量也随之增加，导致代码本身占用的存储空间较递归实现方式多一些，但由于函数调用次数较少，便使得运行时只需要较少的辅助存储单元。此外，若算法的形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若算法的参数传递方式为引用，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

其实，对于一个算法而言，其时间复杂度与空间复杂度往往不是孤立存在的，二者会相互影响，有时候，为了获得较好的时间复杂度，可能会使空间复杂度变高，即通常说的以空间换时间；然而，在位图法与Hash法等算法中，有时候又会为了获得较低的空间复杂度，而使时间复杂度变高。所以，在设计算法（特别是大型算法）时，只有综合考虑各种因素，例如算法的使用频率、数据量的大小、运行环境、系统要求等各方面因素，权衡利弊，才能够设计出符合需求的高效算法。

3.实例分析

下面将分别针对几种常见的时间复杂度进行示例分析，从而给读者更直观的认识。

（1）O(1)

什么样的算法的时间复杂度为O(1)呢？为了说明这个问题，首先看一个简单的交换两个变量值的例子。

上述代码中的代码片段包含了3条语句，每条语句顺序执行，完成了变量i与变量j的交换，因此这一代码片段的执行时间就是这3条语句各自的执行时间之和，与整个算法的输入规模n无关。所以该代码片段的时间复杂度为常数阶，记为O(1)。

有一个需要注意的问题，在求解算法的时间复杂度时，要特别注意区分O(1)与O(n)的情况。下面代码中给出了两个过程，分别是Process_A和Process_B。对于过程Process_A，当输入为任意值时循环次数均为1000，因此时间复杂度为O(1)；对于过程Process_B，当输入n为任意值时循环次数均为n，每次循环体的运行时间均为常数级，因此Process_B的时间复杂度为O(n)（n为输入参数的值）。

（2）O(n)

O(n)代表算法的运算时间和输入呈线性关系。下述代码中的代码段中，语句(1)的频度为1，语句(2)的频度为n，语句(3)的频度为n-1，语句(4)的频度为n-1，语句(5)的频度为n-1，所以全段代码的时间复杂度T(n)=1+n+3(n-1)=4n-2=O(n)。

（3）O(logn)

下述代码所示中，语句(1)的频度为1，设语句(2)的频度为f(n)，由于2^f(n)≤n,那么可知道f(n)≤logn，所以，T(n)=O(logn)。

再看一个二分查找的例子，代码如下所示，其时间复杂度也为O(logn)（n为数组A中元素的个数）。

（4）O(n²)

接下来，再给出几个时间复杂度为O(n²)的例子。在下面代码所示中，第一行是一个赋值语句，所以，只会被执行1次，第二行是一个循环语句，循环总共被执行n+1次，第三行是一个嵌套的循环语句，每次循环执行n+1次，总共n次循环，因此执行次数为n(n+1)，第四行是一个自增语句，执行次数为n²，因此总的执行次数为：T(n)=n²+n(n+1)+1=2n²+n+1。去掉所有的低阶项，再去掉最高阶项的系数就可得到这个代码段的时间复杂度为O(n²)。

再看一个简单例子：示例代码如下所示，语句(1)的频度为n-1，语句(2)的频度为(n-1)*(2n+1)=2n²-n-1，所以该代码段的运行时间为f(n)=2n²-n-1+(n-1)=2n²-2，又因为2n²-2=Θ(n²)，所以该段代码的时间复杂度为T(n)=O(n²)。一般情况下，对循环语句只需要考虑循环体中语句的执行次数，忽略该语句中条件判断、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句（在下述代码中是由语句（2））的频度决定的。

（5）O(n³)

下述代码中，当i=j=k=n时，最内层循环共执行了n⋅(n+1)⋅(n-1)/6次，所以其时间复杂度为O(n³)。通过这个例子不难发现，当代码段中有循环嵌套语句时，算法的时间复杂度是由嵌套层数最多的循环语句块中最内层语句的频度决定的。下述代码段中执行频度最大的是语句(1)，最内层循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(1)的执行次数，则该程序段的时间复杂度为T(n)=O(n³/6+低次项)=O(n³)。

也许有的读者要问，从理论角度分析算法的复杂度不够客观、准确，为什么不通过统计的方式直接运行算法，通过查看程序执行的时间和空间来判断算法的复杂度呢？那样得到的结果是实际运行所需的时间与空间，难道不是更真实、更量化、更能反映出算法的复杂度吗？其实，这种事后统计的方法并非不可行，但是它存在某些方面的局限性：第一，执行难度较大，为了测试程序执行的时间与占用空间，需要人为地去编写测试程序，而这种编写测试程序的工作也是一件较为费时费力的事情；第二，事后统计的方法不能真实反映情况，例如，程序运行的时间不仅与算法本身有关系，还与计算机运行环境（例如硬件配置）、编程语言的选择（如汇编语言就比高级语言更高效）、数据量大小、不同的编译策略（Debug/Release）、输入数据的状态、测试数据量的大小等存在着紧密的联系。所以，大多数算法的时间复杂度都是通过理论分析得出，而非编程实现算法运行后统计所得。

读到这个地方，很多读者可能会产生疑问，现在计算机硬件的运行速度已经很快了，为什么还要不断地追求低的时间复杂度呢？在此，给大家举一个简单的例子说明一下，用通俗的话来描述，假设n=1所需的时间为1秒。那么当n=10,000时。

可见算法的时间复杂度对其执行时间影响有多大。目前，由于参考模型、海量数据等影响因素，世界上最快的处理器仍然无法完全准确无误地预测天气、地震等，所以，虽然提高计算机处理能力能够对算法的执行速度有良好的促进作用，但是对于像n²或者n!乃至更高的时间复杂度的应用而言，改进算法降低其复杂度，发挥的效果会比提升硬件计算能力更大。