html5中文学习网

您的位置: 首页 > 网络编程 > 网页编辑器 » 正文

科学知识:时间复杂度计算方法_其它综合_脚本之家

[ ] 已经帮助:人解决问题

一、定义5MTHTML5中文学习网 - HTML5先行者学习网

(1)如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。我们常用大O表示法表示时间复杂性,称之为大O记法。5MTHTML5中文学习网 - HTML5先行者学习网
(2)一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。常见的时间复杂度高低顺序如下:5MTHTML5中文学习网 - HTML5先行者学习网
O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < O(2^n) < O(n!) < O(n^n)5MTHTML5中文学习网 - HTML5先行者学习网

二、时间复杂度计算步骤5MTHTML5中文学习网 - HTML5先行者学习网

⑴ 找出算法中的基本语句;5MTHTML5中文学习网 - HTML5先行者学习网
算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。5MTHTML5中文学习网 - HTML5先行者学习网
⑵ 计算基本语句的执行次数的数量级;5MTHTML5中文学习网 - HTML5先行者学习网
只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。5MTHTML5中文学习网 - HTML5先行者学习网
⑶ 用大Ο记号表示算法的时间性能。5MTHTML5中文学习网 - HTML5先行者学习网
将基本语句执行次数的数量级放入大Ο记号中。5MTHTML5中文学习网 - HTML5先行者学习网
如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。5MTHTML5中文学习网 - HTML5先行者学习网

三、时间复杂度计算规则5MTHTML5中文学习网 - HTML5先行者学习网

(1)对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间5MTHTML5中文学习网 - HTML5先行者学习网
(2)对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"5MTHTML5中文学习网 - HTML5先行者学习网
求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))5MTHTML5中文学习网 - HTML5先行者学习网
特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))5MTHTML5中文学习网 - HTML5先行者学习网
(3)对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间5MTHTML5中文学习网 - HTML5先行者学习网
(4)对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"5MTHTML5中文学习网 - HTML5先行者学习网
乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))5MTHTML5中文学习网 - HTML5先行者学习网
(5)对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度5MTHTML5中文学习网 - HTML5先行者学习网

(责任编辑:)
推荐书籍
推荐资讯
关于HTML5先行者 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 人才招聘 - 帮助