文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 天文/地理 > 时间复杂度和空间复杂度
侵权投诉

时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度合称为算法的复杂度。

时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度合称为算法的复杂度。

1.时间复杂度

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

(2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

时间频度不同,但时间复杂度可能相同。如:T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。

按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

(3)最坏时间复杂度和平均时间复杂度 最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长。

在最坏情况下的时间复杂度为T(n)=0(n),它表示对于任何输入实例,该算法的运行时间不可能大于0(n)。 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,算法的期望运行时间。

指数阶0(2n),显然,时间复杂度为指数阶0(2n)的算法效率极低,当n值稍大时就无法应用。

(4)求时间复杂度

【1】如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 x=91; y=100;

while(y>0) if(x>100) {x=x-10;y--;} else x++;

解答: T(n)=O(1),

这个程序看起来有点吓人,总共循环运行了1000次,但是我们看到n没有?

第1页

你可能喜欢

热门文档

相关文档

  • 算法复杂度——时间复杂度和空间复杂度

    2 3 2、类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算 法所耗费的存储空间, 它也是问题规模 n 的函数。 渐近空间复杂度也...

  • 算法的时间复杂度和空间复杂度

    3、算法的时间复杂度和空间复杂度 、 所谓算法的时间复杂度,是指执行算法所需要的计 算工作量。 一个算法的空间复杂度,一般是指执行这个算法所 需要的内存空间...

  • 排序算法的时间复杂度和空间复杂度

    排序算法的时间复杂度和空间复杂度 常用的内部排序方法有:交换排序(冒泡排序、快速排序) 、选择排序(简单选择排序、堆排序) 、插入排 序(直接插入排序、希尔排序)...

  • 常用的排序算法的时间复杂度和空间复杂度

    常用的排序算法的时间复杂度和空间复杂度_数学_自然科学_专业资料 暂无评价0人阅读0次下载举报文档 常用的排序算法的时间复杂度和空间复杂度_数学_自然科学_...

  • 第五讲 时间复杂度和空间复杂度3

    第五讲 时间复杂度和空间复杂度3_资格考试/认证_教育_PPT专区。数据结构和算法 作者:小甲鱼 让编程改变世界 Change the world by program 函数调用的时间复杂度分...

  • 时间空间复杂度

    本质上,不论时间复杂度还是空间复杂度都反应的是问题本身的复杂度。一个计算要不就需要很大的存储空间来减少计算时间;要不就需要较长的计算时间来节约存储空间。 ...

  • 第四讲 时间复杂度和空间复杂度2

    第四讲 时间复杂度和空间复杂度2_资格考试/认证_教育_PPT专区。我们说好的时间复杂度和空间复杂度呢?历来大学老师在讲解这两个概念,都是直接登堂入室,导致八成学...

  • 时间与空间复杂度

    一个算法的评价主要从时间复杂度和空间复杂度来考虑。 1、时间复杂度 (1) 时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能...

  • 时间复杂度的计算

    2、空间复杂度 与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度 量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email