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

ISSN1009-3044
Computer与技术电脑知识与技术ComputerKnowledgeKnowledgeandandTechnologyTechnology电脑知识
Vol.7,No.19,July2011.第7卷第19期(2011年7月)doc.guandang.net时间复杂度的几种计算方法
刘怀愚,朱昌杰,李璟
(淮北师范大学计算机科学与技术学院,安徽淮北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人工智能及识别技术本栏目责任编辑:唐一东
65 5993+1606 时 间复杂度的几种计算方法 刘愚, 昌李 怀朱杰, 臻( 北师范大学 计算机科学与技术学院 ,淮 安徽 淮北250)300 摘要:法的时 间复 杂度是...
(n2) 3 时间复杂度的计算方法时间复杂的推导方法一般如下 : 第一步 : 用...间复杂度为 O (n2)。 4 总结 数。 时间复杂度一般分为以下几种 , 分别...
时间复杂度的计算学习数据结构时, 觉得时间复杂度计算很复杂, 怎么也看不懂, 差不多三年之后, 还是不懂,马上就要找工作了,赶紧恶补一下吧: 首先了解一下几个概...
时间复杂度的计算 算法复杂度是在 《数据结构》 这门课程的第一章里出现的, ...首先了解一下几个概念。一个是时间复杂度,一个是渐近时间复杂度。前者是某个...
算法的时间复杂度的计算 1页 1下载券 时间复杂度的几种计算方... 3页 1下载...讨论方法与时 间复杂度类似,不再赘述。 (3)渐进时间复杂度评价算法时间性能 ...
一个算法的效率,也大概明白怎么回事,知道如果没 有循环的一段程序的复杂度是...时间复杂度的几种计算方... 3页 1下载券 时间复杂度的几种计算方... 3页...
如何计算时间复杂度_数学_自然科学_专业资料。如何计算时间复杂度求解算法的时间复杂...在计算算法时间复杂度时有以下几个简单的程序分析法则: 1.对于一些简单的输入...
数据结构中算法的时间复杂度的计算方法_计算机软件及应用_IT/计算机_专业资料。一...时间复杂度的几种计算方... 3页 1下载券 数据结构时间复杂度的计... 4页...
3.冒泡排序:稳定,时间复杂度 O(n^2) 冒泡排序方法是最简单的排序方法。这种...典型比较排序法时间复杂... 暂无评价 6页 免费 时间复杂度的几种计算方... ...
的时间复杂度和空间复杂度 所谓算法的时间复杂度,是指执行算法所需要的计算工作...2.几种常见算法 几种常见算法 2.1 冒泡排序(Bubble Sort) 冒泡排序方法是最...
热门文档