算法复杂度分析.doc

《算法复杂度分析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析•时间复杂度分析2010-09-2010:22:47关键概念要分析算法的复杂度，通常需要分析循环的运行.一，假如，某个循环体的复杂度是O⑴，那么这个循环的时间复杂度就是O(n).for(inti=0;i

2、){count+=2;〃一些列复杂度为0(1)的步骤•…}时间复杂度还是O(n)二，如果循环体的复杂度是对数级的如下intcount=1;while(count

3、{〃一些列复杂度为O⑴的步骤….}}在这种情况下应该先计算内层循环的时间复杂度，然后用内层的复杂度乘以外层循环的次数.最内层循环体的时间复杂度都是O⑴所以循环n次也就是O(n)在乘以最外层for的n次.所以得出结论2层嵌套循环的时间复杂度=O(1)*n*n=O(n2)在分析嵌套循环复杂度的时候必将内股循环和外层虚幻都考虑进来四，方法调川的复杂度分析假如有如下代码for(intcount=0;count

4、头是一个方法的调川，那么这个循环体的时间复杂度如何呢！这个方法就是打印的和.所以必须先计笄方法体的的时间复杂度.publicvoidprintsum(intcount){intsum=1;for(inti=0;isum+=i;}System.out.print(sum);}记住，只冇可运行的语何才会增加时间复杂度，因此，上面方法里的内容除了循环Z外,其余的可运行语句的复杂度都是0(1),所以printsum的时间复杂度二for的0(n)+0(1)=忽略常量=0(n)但是冋想一下，我们让程序打印1-n的和不需要

5、用for循环记得初中数学课上老师就给岀了个公式num=n*(n+1)/2改publicvoidprintsum(intcount){intsum=1;sum=count*(count+1)/2;System.out.print(sum);}此时的printsum方法的阶次就是0(1)>意味着最外层调用此方法的循环复杂度就从0(n2)改良为0(n)这是一个很大的提高.从这点就可以看出简单算法和高效算法Z间的差别了.五如果一个方法体是山多个方法调用and多个循环组成的，那么其复杂度乂如何!publicvoidsu

6、ixiangMethod(intn){printsum(n);//1.1for(inti=0;iprintsum(n);}for(inti=0;ifor(intk=0;kSystem.out.print(i,k);}}suixiangMethod方法的时间复杂度希要计算方法体的各个成员的复杂度？也就是1.1+1.2+1.3=O(1)+O(n)+O(n2)忽略常数和非主要项==0(n2)