时间复杂度的几种计算方法

ISSN1009-3044

Computer与技术电脑知识与技术ComputerKnowledgeKnowledgeandandTechnologyTechnology电脑知识

Vol.7,No.19,July2011.第7卷第19期(2011年7月)www.wendangwang.com时间复杂度的几种计算方法

刘怀愚，朱昌杰，李璟

（淮北师范大学计算机科学与技术学院，安徽淮北235000）

摘要：算法的时间复杂度是反映算法优劣的重要指标，是《数据结构》的重要理论基础，是学习和教学过程中贯穿始终的主要线索。但是由于概念的抽象和计算方法的繁琐，使算法时间复杂度成为最难理解和掌握的问题之一。在总结教学经验的基础上，该文提出几种常用的时间复杂度计算方法，使对该知识点的教学和学习变得系统和简单。

关键词：数据结构；时间复杂度；渐进时间复杂度；迭代法

中图分类号：TP301文献标识码：A文章编号：1009-3044(2011)19-4636-03

SeveralCalculationMethodsofTimeComplexity

LIUHuai-yu,ZHUChang-jie,LIJing

(SchoofofComputerScienceandTechnology,HuaibeiNormalUniversity,Huaibei235000,China)

Abstract:Timecomplexityisanimportantindexinalgorithmintermsofreflectingthequalityofthealgorithm.TimecomplexityisalsoanimportanttheoreticalbasisinDataStructure,thusisregardedasamajorcluethroughoutlearningandteachingprocess.However,duetotheabstractnessoftheconceptandthetediouscalculationmethod,timecomplexityofthealgorithmbecomesamostdifficultissuetoun-derstandandmaster.Thispaper,onthebasisofsummingupteachingexperiences,presentsseveralcommonlyusedmethodsforthetimecomplexitywiththeaimofsimplifyingtheteachingandlearningoftheknowledgepointinasystematicapproach.

Keywords:Datastructure;TimeComplexity;AsymptoticTimeComplexity;Iterationmethod

1算法时间复杂度的基本概念

1.1算法的执行时间和语句频度

在已证明算法正确性的前提下，评价算法的好坏主要是关注算法在时间和空间上性能的优劣。算法时间性能的分析是通过计算算法时间复杂度实现的，其关键就是计算算法的执行时间。一个算法的执行时间，就是算法中每条语句的执行时间的总和。但是在算法实际运行过程中，每次执行所耗费的时间会受到诸如问题规模、输入特性和具体硬件环境等各种外界因素的影响，想得到一个绝对准确的执行时间是几乎不可能的。为此，在进行算法执行时间的计算时一般都忽略硬件及环境因素，并且假设每次执行时硬件条件和环境条件都是完全一致的，每条语句执行一次所需的时间均是单位时间[1]。

算法中一条语句的执行时间取决于该语句的执行次数和执行一次所需的时间。语句执行次数被称为语句频度，执行一次的时间被假设为单位时间，因此算法的执行时间就可以看作是该算法中所有语句的语句频度之和[2]。

1.2算法时间复杂度和渐进时间复杂度

算法时间复杂度的本质是算法的执行时间，也就是算法中所有语句的频度之和。语句频度就是语句的执行次数，它与算法求解问题的规模大小息息相关。假设对于给定的算法，目前问题规模为n，则语句频度可以表示成一个关于问题规模的函数T(n)，那么算法时间复杂度也就可以用T(n)表示，其含义是算法在输入规模为n时的运行时间。

当问题规模很大时，精确的计算T(n)是很难实现而且也是没有必要的。对于算法时间性能的分析无需非要得到时间复杂度T(n)的精确值，它的变化趋势和规律也能清楚地反映算法的时间耗费。基于此，引入了渐进时间复杂度作为时间性能分析的依据，它的含义就是：在问题规模n趋于无穷大时算法时间复杂度T(n)的渐进上界，即函数T(n)的数量级(阶)[3]。

算法时间复杂度和渐进算法时间复杂度在实际的算法分析过程中是不予区分的，渐进时间复杂度可以简称为时间复杂度，记为T(n)=O(f(n))。其中，

“O”表示取数量级(阶)；

函数f(n)是T(n)的同数量级(阶)函数，即

的执行次数。

按数量级递增排列，常见的时间复杂度有：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n),平方阶O(n2)，立方阶(C为不为零的常数)。它一般是算法中最大的语句频度，是最内层循环语句O(n3)，…，k次方阶O(nk)，指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

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

收稿日期：2011-05-11

作者简介：刘怀愚（1979-），男，安徽淮北人，工学硕士，讲师，研究方向：模式识别；朱昌杰（1963-），男，安徽怀宁人，教授，硕士生导

师，研究方向：信息管理；李璟（1979-），女，安徽省亳州人，硕士，讲师，研究方向：模式识别。

4636人工智能及识别技术本栏目责任编辑：唐一东