Question

设n为整数,求下列各程序段的时间复杂度.（1）i=1；k=2； while（i0） if（x>100）{ x=x-10；

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)?第二次循环(y+2)?第三次循环(y+3)?...第m次循环(y+m)?(y+m)?