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

《算法时间复杂度的计算.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,那么这个算法时间效率比较高，如果是