算法的時間復(fù)雜度

常見的算法時間復(fù)雜度由小到大依次為:

常數(shù)階 O(1) <?對數(shù)階 O(log2n) <?線性階 O(n) <?線性對數(shù)階 O(nlog2n) <?平方階 O(n^2) <?立方階 O(n^3) <?k次方階 O(n^k) <?指數(shù)階 O(2^n)

算法的時間復(fù)雜度取決于：問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)。

計算下列各算法的時間復(fù)雜度

1. x=90;y=100;

   while(y>0)

   ? ? ?if(x>100)

   ? ? ? ? ? {x=x-10;y--;}

   ? ? ?else? x++;

2. for(i=0; i<n; i++)

   ? ? ?for(j=0; j<m; j++)

   ? ? ? ? ? a[i] [j] =0;

3. s=0;

   for(i=0; i<n; j++)

   ? ? ?for(j=0; j<n; j++)

   ? ? ? ? ?s+=B[i] [j];

   sum=s;

4. i=1;

   while(i<=n)

   ? ? ?i=i*3;

5. x=0;

   for(i=1; i<n; i++)

   ? ? for(j=1; j<=n-i; j++)

   ? ? ? ? x++;

6. x=n; //n>1

   y=0;

   while(x>=(y+1)*(y+1))

   ? ? ? ?y++;

   答：

   第一:? ?O(1)? ? 理由：算法執(zhí)行的再大，算法的時間復(fù)雜度都是1。

   第二：O(n*m)? ?理由：for循環(huán)兩次，一次n，一次m，所以是n*m。

   第三：O(n^2)? ?理由：for循環(huán)兩次，兩次都說n，所以n的2次方。

   第四：O(log2n)? ?理由：n等于1，2，3時循環(huán)1次，n等于4，5，6 ....12時循環(huán)2次，以此類推得出 log2n。

   第五：O(n^2)? 理由：兩次for循環(huán)，循環(huán)n次，所以n的2次方。

   第六：O(√n)? ?理由：x大于等于(y+1)的平方，所以循環(huán)更號n次。