时间复杂度例题

1、设n为正整数，试确定下列各程序段中前置以记号@的语句的频度。评析：频度时间复杂度注意：（1）、（2）、（3）三个程序段中任何两段都不等效(即k和i的终值不相同)（1）i=1;k=0;while(i=n-1){@k+=10*i;i++;}解：k+=10*i的意思是k=k+10*i时间复杂度是O(n);@k+=10*i的频度准确值为n-1（2）i=1;k=0;do{@k+=10*i;i++;}while(i=n-1);解：时间复杂度是O(n);@k+=10*i的频度准确值为n。准确值T(n)=n-1（3）i=1;k=0;while(i=n-1){i++;@k+=10*i;}解：时间复杂度是O(n);@k+=10*i的频度准确值为n-1。（4）k=0;for(i=1;i=n;i++){for(j=i;j=n;j++)@k++;}解：这是双重循环，应当是O(n2);@k++的频度准确值为:n+n-1+n-2+……+3+2+1=n(n+1)/2◆（5）for(i=1;i=n;i++){for(j=1;j=i;j++){for(k=1;k=j;k++)@x+=delta;}}解：这是三重循环，应当是O(n3);但@x+=delta的频度准确值为:niii12/)1(=n(n+1)(n+2)/6（6）i=1;j=0;while(i+j=n){@if(ij)j++;elsei++;}每次循环（i+j）的值增1，故循环共执行n次，if语句执行n次此程序实质上是一个双重循环，对每个y(0)值，@语句从x=91开始直到x=101都执行，共执行11次，其中10次是执行x++。2、假设n为2的乘幂，并且n2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。intTime(intn){count=0;x=2;while(xn/2){x*=2;count++;}return(count)}◆（7）x=n;y=1;//n是不小于1的常数while(x=(y+1)*(y+1)){@y++;}y的增量就是频度,且（y+1）2≤n，频度为不大于n-1的最大整数◆（8）x=91;y=100;while(y0){@if(x100){x-=10;y--;}//x-=10的意思是x=x-10elsex++;}