算法的时间复杂性

徐素梅

（安徽理工大学 理学院，安徽 淮南 232001）

一个算法是一个有限指令的集合。这些指令确定了解决某一问题的运算或操作程序。问题是要求回答的提问。通常有几个参数或自变量，他们的值是特定的，取自问题的定义域，问题的描述即对其参数进行描述，之处其解是满足什么性质的命题。给问题的全体参数都指定了确定的值，便得到问题的一个实例。例如“y+z=?”是加法问题，而”4+7=?”是加法实例。当然，一个问题一般可以包含多个实例。一个计算机程序即使是按照正确的算法编写的，对于一些输入来时也许是毫无用处的，因为这个程序的执行时间太长，或者程序的数据、变量等占用的存储空间太大。算法分析是指通过分析得到算法所需的时间和空间的估计量，算法的复杂度是指执行算法所需的时间和空间的量。因此，本文叙述一下算法执行所需时间的问题。

1 时间复杂性

图1

用微积分可以证明，上列函数中给每个函数都小于其对于数字的函数，即每个函数与其后数字代表的函数的比在n无限增长时趋于0.图1显示了这些函数的图像，图1中函数值的每个刻度都是它前面刻度的两倍。

1.1 时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

1.2 计算方法

a、一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数 f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））_

分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。

b、算法的时间复杂度

若要比较不同的算法的时间效率，受限要确定一个度量标准，最直接的办法就是将计算法转化为程序，在计算机上运行，通过计算机内部的计时功能获得精确的时间，然后进行比较。但该方法受计算机的硬件、软件等因素的影响，会掩盖算法本身的优劣，所以一般采用事先分析估算的算法，即撇开计算机软硬件等因素，只考虑问题的规模（一般用用自然数n表示），认为一个特定的算法的时间复杂度，只采取于问题的规模，或者说它是问题的规模的函数。为了方便比较，通常的做法是，从算法选取一种对于所研究的问题（或算法模型）来说是基本运算的操作，以其重复执行的次数作为评价算法时间复杂度的标准。该基本操作多数情况下是由算法最深层环内的语句表示的，基本操作的执行次数实际上就是相应语句的执行次数。一般T（n）=Of（n）

例如：

则有T（n）=n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方为T（n）的同数量级

则有 f（n）=n 的三次方，然后根据 T（n）/f（n）求极限可得到常数 c则该算法的 时间复杂度：T（n）=O（n的三次方）

O（1）

1.3 分类

按数量级递增排列，常见的时间复杂度有：

常数阶 O（1），对数阶 O（log2n），线性阶 O（n），k 次方阶 O（nk），指数阶 O（2n）。随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

线性对数阶 O（nlog2n），平方阶 O（n2），立方阶 O（n3），...，

假设是“标准”的计算机，算法的时间的复杂性的考虑可以在输入规模一定的情况下，用算法使用的基本操作（解问题的关键操作，操作次数随输入规模的增大而增加）次数来表示。而不用计算机实际运行的时间来表示，这时因为执行基本操作时，不同的计算机需要的时间不同，而且把所有运算分解成计算机使用的基本字位运算是相当复杂的。

在所有输入规模为n的情况下，可以找到执行算法所需的最短时间和最长时间，分别称为输入规模为n的最好时间复杂性和最坏时间复杂性。平均时间是指在一组有限的规模为n的输入中执行算法所需的时间。平均时间复杂性分析比最坏情况分析复杂的多。

图2给出了描述算法时间复杂性的几个常用术语

图2

变量计数：

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是（6），其频度为f（n）=n2，所以该程序段的时间复杂度为T（n）=O（n2）。当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f（n）决定的。

2 空间复杂度

空间复杂度（Space Complexity）是对一个算法在运行过程中临时占用存储空间大小的量度。比如插入排序的时间复杂度是O（n2），空间复杂度是O（1）而一般的递归算法就要有O（n）的空间复杂度了,因为每次递归都要存储返回信息

一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。 类似于时间复杂度的讨论，一个算法的空间复杂度(SpaceComplexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地”进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。

分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般都比较简短，算法本身所占用的存储空间较少，但运行时需要一个附加堆栈，从而占用较多的临时工作单元；若写成非递归算法，一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。

空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量，作：S（n）=Of（n）。一个空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表不开始进行的一次非递归调用)。

渐进时间复杂度评价算法时间性能主要用算法时间复杂度的数量级（即算法的渐近时间复杂度）评价一个算法的时间性能

3 联系

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间；反之，当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。

图3 常用的算法的时间复杂度和空间复杂度

4 NPC问题

能使用具有多项式最坏情况复杂性的算法解决的问题称为易处理的，否则，称为不易处理的。不过，如果在大O估计中的多项式次数高（如100次），多项式的次数特别大，算法可能会花特别长的时间来解决问题。对于实际应用中出现的不易处理的问题，如果存在求近似解的快速算法，甚至还能保证近似解与精确解相差不太大，通常不求其精确解，而求其近似解。

易处理的问题属于P问题，至今既没有找到多项式算法，又不能证明它不存在多项式算法。这类问题称为NPC问题。还有一类重要问题，只要其中任何一个问题能用一个多项式时间最坏情况算法解答，称为其NPC问题简称NPC问题。

5 小结

随着科学技术的不断发展，计算机速度和内存空间获得巨大的增长，再加上使用能做并行处理的算法，以前认为的不能同时兼顾时间复杂性和空间复杂性的问题将迅速的减少，极大的减少了计算机所花的时间和占有的存储量，空间复杂性与实现算法时间使用的特定数据结构紧密相连，我相信在即将的未来随着科学技术的不断进步，一些繁复的NPC问题和极度复杂不能兼顾时间与空间的问题将面临攻克。算法复杂度将不再是解问题的巨大障碍。

［1］卜月华，吴建专，顾国华，殷翔，图论及其应用[M].东南大学出版社，2002.

［2］蒋长浩,图论与网络流[M].中国林业大学出版社，2001.

［3］殷剑宏,吴开亚.[M]中国科学技术大学出版社，2003

［4］Back T，Schwefel H P.An overview of evolutionary algorithms for parameter optimization[J].Evolutionary Computation.1993.

［5］Fogel L J，Owens A J，Walsh M J.Artificial Intelligence through Simulated Evolution[M].New York：Wiley，1996.

［6］Holland J H.Adaptation in Natural and Artificial Systems[M].2nd ed.Cambridge.MA：MIT Press，1992.