Question

设n为整数，求下列各程序段的时间复杂度。

设n为整数，求下列各程序段的时间复杂度。（1）i=1；k=2； while（i<n）{ k=k+10*i； i=i+1； } （2）i=1；j=0； while（i+j<=n） if（i>j）j=j+1； else i=i+1； （3）x=91；y=100； while（y>0） if（x>100）{ x=x-10； y=y-1； }else x=x+1； （4）x=n； while（x>=（y+1）*（y+1）） y=y+1；

Answer 1

(1)循环从i=1到i=n-1,所以循环的次数是n-1,所以时间复杂度是O(n-1),即O(n)(2)循环从i=1,j=0到i=n/2,j=n/2,由于每次i和j只有一个变量增加,所以总的循环次数是n次.时间复杂度是O(n)(3)x=91到x=101,循环10次.然后y=100到99,x=91,然后x从91到101,循环10次,y从99到98.如此往复直到y=1,y每减1,x就循环10次,所以总共循环10*100=1000次,所以时间复杂度是O(1000),即O(1)(4)第一次循环(y+1)�0�5第二次循环(y+2)�0�5第三次循环(y+3)�0�5...第m次循环(y+m)�0�5(y+m)�0�5<=n,得m=logn - y所以循环次数是logn - y,时间复杂度是O(logn)

Answer 2

第一个时间复杂度是n第二个时间复杂度是n的平方第三个时间复杂度是n的立方第四个时间复杂度好像是2^n