数据结构算法时间复杂度的计算

《数据结构算法时间复杂度的计算》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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、分析：1.语句intnum1,num2;的频度为1；语句i=0;的频度为1；语句i

4、以极限等于3。T(n)=O(n*log2n)简化的计算步骤再来分析一下，可以看出，决定算法复杂度的是执行次数最多的语句，这里是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

6、。另外，一个未知数的数量级为其最接近的数量级，即最大可能的数量级。求极限的技巧要利用好1/n。当n趋于无穷大时，1/n趋向于0--------------------------------------------------------------------------------一些规则(引自：时间复杂度计算)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)一个特例（问题规模为常量的时间复杂度）在

7、大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、--------------------------

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

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

11、较好一般较

12、差其中c是一个常量，如果一个算法的复杂度为c、log2n、n、n*log2n,那么这个算法时间效率比较高，如果是2n,3n,n!,那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。----------------------------------------------------------------------------------------