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

《算法时间复杂度的计算.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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.计算出T

2、(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、,num2;的频度为1；语句i=0;的频度为1；语句i

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

5、--------一些补充说明最坏时间复杂度   算法的时间复杂度不仅与语句频度有关，还与问题规模及输入实例中各元素的取值有关。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的运行时间不会比任何更长。求数量级即求对数值(log)，默认底数为10，简单来说就是“一个数用标准科学计数法表示后，10的指数”。例如，5000=5x103(log5000=3)，数量级为3。另外，一个未知数的数量级为其最接近的数量级，即最大可能的数量级。求极限的技巧要利用好1/n。当n趋于无穷大时，1/n趋向于0--------------------------------------

6、------------------------------------------一些规则(引自：时间复杂度计算)1)加法规则T(n,m)=T1(n)+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)一个经验规则复杂度与时

7、间效率的关系：c

8、--------------------------

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

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

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