Question

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

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)

Answer 2

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