算法时间复杂度的计算.doc

算法时间复杂度的计算.doc

ID:48918982

大小:44.50 KB

页数:7页

时间:2020-02-06

算法时间复杂度的计算.doc_第1页
算法时间复杂度的计算.doc_第2页
算法时间复杂度的计算.doc_第3页
算法时间复杂度的计算.doc_第4页
算法时间复杂度的计算.doc_第5页
资源描述:

《算法时间复杂度的计算.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、.算法时间复杂度的计算[整理] 基本的计算步骤时间复杂度的定义   一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度(O是数量级的符号),简称时间复杂度。根据定义,可以归纳出基本的计算步骤1.计算出基本操作的执行次数T(n)   基本操作即算法中的每条语句(以;号作为分割),语句的执行次

2、数也叫做语句的频度。在做算法分析时,一般默认为考虑最坏的情况。2.计算出T(n)的数量级   求T(n)的数量级,只要将T(n)进行如下一些操作:   忽略常量、低次幂和最高次幂的系数   令f(n)=T(n)的数量级。3.用大O来表示时间复杂度   当n趋近于无穷大时,如果lim(T(n)/f(n))的值为不等于0的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。一个示例:(1)intnum1,num2;(2)for(inti=0;i

3、   for(intj=1;j<=n;j*=2){(5)        num2+=num1;(6)    }(7)}分析:1.语句intnum1,num2;的频度为1;语句i=0;的频度为1;语句i

4、                   =2*(1/n)*(1/log2n)+4*(1/log2n)+3当n趋向于无穷大,1/n趋向于0,1/log2n趋向于0所以极限等于3。T(n)=O(n*log2n)简化的计算步骤再来分析一下,可以看出,决定算法复杂度的是执行次数最多的语句,这里是num2+=num1,一般也是最内循环的语句。并且,通常将求解极限是否为常量也省略掉?于是,以上步骤可以简化为:1.找到执行次数最多的语句2.计算语句执行次数的数量级3.用大O来表示结果继续以上述算法为例,进行分析:1.执行次数最多的

5、语句为num2+=num12.T(n)=n*log2nf(n)=n*log2n3.//lim(T(n)/f(n))=1T(n)=O(n*log2n) --------------------------------------------------------------------------------一些补充说明最坏时间复杂度..   算法的时间复杂度不仅与语句频度有关,还与问题规模及输入实例中各元素的取值有关。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的运行时间不会比任何更

6、长。求数量级即求对数值(log),默认底数为10,简单来说就是“一个数用标准科学计数法表示后,10的指数”。例如,5000=5x103(log5000=3),数量级为3。另外,一个未知数的数量级为其最接近的数量级,即最大可能的数量级。求极限的技巧要利用好1/n。当n趋于无穷大时,1/n趋向于0--------------------------------------------------------------------------------一些规则(引自:时间复杂度计算)1)加法规则T(n,m)=T1(n

7、)+T2(n)=O(max(f(n),g(m))2)乘法规则T(n,m)=T1(n)*T2(m)=O(f(n)*g(m))3)一个特例(问题规模为常量的时间复杂度)在大O表示法里面有一个特例,如果T1(n)=O(c),c是一个与n无关的任意常数,T2(n)=O(f(n))则有T(n)=T1(n)*T2(n)=O(c*f(n))=O(f(n))也就是说,在大O表示法中,任何非0正常数都属于同一数量级,记为O(1)。4)一个经验规则复杂度与时间效率的关系:c

8、(c是一个常量)

9、--------------------------

10、--------------------------

11、-------------

12、         较好                    一般             较差其中c是一个常量,如果一个算法的复杂度为c、log2n、n、n*log2n,那么这个算法时间效率比较高,如果是

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。