算法时间复杂度的分析方法研究

周士红

广东培正学院，广东广州，510830

0 引言

评价一个算法性能的指标有很多，比如易读性、健壮性、可维护性、可扩展性、效率等等，其中效率是衡量算法性能的核心和灵魂。用来度量算法效率的两个指标为时间性能和空间性能，其中时间性能就是指算法所需要的执行时间。不考虑与计算机软硬件有关的因素，影响算法时间性能的最主要因素是问题规模（即输入量的多少，用n来表示）[1]。几乎所有的算法对于规模更大的输入都需要运行更长的时间，所以算法执行过程中所需要的时间T是问题规模n的函数，记作T(n)。但是由于受到各种因素的影响，要精确地表示算法的运行时间函数是非常困难的，所以可以采用时间复杂度这一指标来度量算法执行时间的增长趋势。

1 基本语句与时间复杂度

算法是由若干条语句构成的，若要计算这个算法的执行时间，其实就是求算法中每条语句的执行时间的总和[2]。而执行一条语句所用的时间为执行次数与执行一次所需时间的乘积，而一条语句执行一次所需的单位时间是一定的，所以对算法的执行时间影响最大的是语句的执行次数，也称为语句的频度[3]。在一个算法的所有语句中，某些语句的执行次数对整个算法的执行次数起决定性的影响，这样的语句称为基本语句。当问题规模充分大时，基本语句对算法执行时间的贡献最大，所以可以用基本语句的执行次数来衡量算法执行时间的增长趋势，这种方式简称算法的时间复杂度，记作T(n)=O(f(n))[4]。

常见的时间复杂度有常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)等[5]。按数量级由小到大依次排列为：O(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n2)＜O(n3)＜O(nk)＜O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率就会不断降低。一般来说，在设计算法时要设计具有多项式时间复杂度的算法，而具有指数时间复杂度的算法，只有当问题规模足够小的时候才可使用[5]。

2 算法中语句的结构

在数据结构与算法的前序课程中我们学过程序流程的三种控制结构分别为顺序控制结构、选择控制结构和循环控制结构，算法的基本语句就存在于这三种结构中。下面我们分析以下三种结构对算法时间复杂度的影响。

2.1 顺序结构的时间复杂度

以上算法由三条顺序结构的语句组成，每条语句执行次数都为1，即每条语句都可以在单位时间内完成，所以该算法的时间复杂度为T(n)=O(1)。不失一般性，因为顺序结构的执行过程都是一步一步完成的，所以其时间复杂度为常数阶。

2.2 选择结构的时间复杂度

以上算法中有一个简单的选择结构，每条语句的执行次数为1，所以也是可以在单位时间内完成，所以时间复杂度为T(n)=O(1)。不失一般性，因为选择结构的执行过程也是一步一步完成的，所以其时间复杂度为常数阶。

2.3 循环结构的时间复杂度

在以上算法中语句x++为基本语句，其执行次数受循环变量i的影响，即从0到n-1一共执行n次，所以时间复杂度为T(n)=O(n)。

通过以上分析可以看出，顺序结构和选择结构的时间复杂度都为常数阶。当算法中有循环结构，并且问题规模足够大时，顺序结构和选择结构对算法执行时间的影响几乎可以忽略不计。所以以下主要针对循环结构的时间复杂度进行计算方法的分析。

3 算法时间复杂度的计算方法

通常情况下，算法分为非递归算法和递归算法，以下分情况讨论。

3.1 非递归算法的时间复杂度的分析

通过上面的分析可以得出，当问题规模足够大时，对算法时间复杂度起决定性作用的是循环结构。循环结构是由两部分构成的，包括循环条件和循环体。根据循环条件与循环体之间是否有关系可以将循环结构分为：①循环条件和循环体之间相互独立；②循环条件之间有关系，但与循环体独立；③循环条件与循环体之间有关系。不同类型的循环结构，其时间复杂度有不同的分析方法。

3.1.1 直接分析法

当循环结构中循环条件与循环体相互独立，并且循环条件的执行次数比较容易计算时，可以直接分析算法的时间复杂度。例如有以下算法。

例1是给定 n个元素的数组a[n]，求其中奇数有多少个。由代码段可以看出，该函数中只有一层for循环，而该循环执行了n次，因此时间复杂度为T(n)=O(n)。

例2算法中的循环结构是双重嵌套循环，并且循环条件和循环体之间都是相互独立的。可以直观地看出，每当外层循环的i取一个值时，内层循环都执行n次，所以该算法的时间复杂度为T(n)=O(n m)。

3.1.2 求乘积法

在嵌套循环中，当循环条件之间有关系，但与循环体独立时，可以用乘积法计算时间复杂度。在例3算法中，内层循环条件j的执行次数受外层循环条件i的执行次数的影响，所以我们无法非常直接地分析算法的时间复杂度。

分析以上算法，其中m=m+1为基本语句，与循环变量i和j没有关系，所以假定用1来代表该基本语句，其执行次数为：。当问题规模足够大时，可以忽略n的影响，所以其时间复杂度为T(n)=O(n2)。

3.1.3 转换法

在某些算法中，因为循环条件与循环体中的某些语句有关系，可能导致无法非常直观地计算语句的执行次数。但是有些循环结构之间可以进行相互转换，转换后可以更方便计算。例如有以下算法。

对于以上算法，因为循环条件和循环体中都有i，所以无法直观地计算语句的执行次数。但是while循环和for循环在某些情况下是可以相互转化的，所以例4可以转换为如下算法：

在转换后的算法中，x++为基本语句。假设基本语句的执行次数为T(n)，则执行完后有i=2T(n)。而i<=n，所以2T(n)≤n，即T(n)≤log2n，所以算法的时间复杂度为T(n)=O(log2n)。

3.1.4 数学归纳法

在某些更为复杂的算法中，当循环次数与循环体中的某些语句执行有联系，并且循环结构无法进行转换或者转换后也无法使计算变得简单，此时可以用数学归纳法分析循环变量与语句执行次数的关系，进而得出算法的时间复杂度。例如有以下算法。

但是转换后也无法直接计算时间复杂度，所以可以采用数学归纳法寻找循环次数与sum之间的关系。对于例5假定循环次数为m，则有：

当m=1时，i=1，sum=0+1；

当m=2时，i=2，sum=0+1+2；

当m=3时，i=3，sum=0+1+2+3；

……

当执行m次时，i=m，sum=0+1+2+3+……+m=。

整理后得m(m+1)=2(n-1)，即m2+m=2n-2。

m2为负值，不符合要求，舍弃，只取m1。所以可以看出该算法的时间复杂度为T(n)=O()。

3.1.5 求和法

当算法中存在多个并列的循环结构时，可以用求和法来计算时间复杂度。例如有以下算法。

在以上算法中，并列存在两个循环结构。第一个循环结构为双重循环，其时间复杂度用直接分析法可以得出为O(n2)。第二个循环结构为单层循环，其时间复杂度也可以直接得出为O(n)。所以整个算法的时间复杂度为T(n)=O(n)+O(n2)。当问题规模足够大时，可以忽略O(n)对O(n2)的影响，因此整段代码的时间复杂度为T(n)=O(n2)。

3.2 递归算法的时间复杂度的分析

递归算法简单来说就是一个函数直接或间接调用自身的一种方法。通过递归，可以将一个原本非常大型的问题转换为一个与原有问题相似但是规模比较小的问题来求解。对于递归算法通常采用递推法来求解其时间复杂度，例如有以下算法。

假设该函数的运行时间为T(n)。函数中s=1的运行时间为O(1)，s=n*fun(n-1)的运行时间为T(n-1)+O(1)，即：

由此可得：

所以该递归函数的时间复杂度为T(n)=O(n)。

4 总结

对于算法效率的分析有事前分析和事后统计两种方法。事后统计指的是通过编写程序实现算法后进行定量分析，这种方式需要花费较多的时间和精力，并且容易受到计算机软硬件等环境因素的影响。所以通常采用事前分析的方法来估算，而时间复杂度就是一个通过增长趋势来度量算法执行时间的指标。算法时间复杂度的分析贯穿在数据结构教材中各种算法的性能分析中，学会分析算法的时间复杂度可以帮助我们设计出更高效、更优化的算法。但是在教学过程中，由于时间复杂度概念比较抽象，并且对于某些算法来说其计算过程比较复杂，所以时间复杂度一直是教学过程中的难点。论文对算法时间复杂度的相关知识和理论进行了简单介绍，通过分析得出了在算法中对其时间复杂度影响最大的是循环结构，然后根据循环结构不同的类型给出了对于时间复杂度不同的求解方法，使学生对算法时间复杂度的理解和掌握更为系统。