從循環和條件語句計算時間複雜度

-1

我計算每個循環的時間複雜度O(n)。從代碼的每一行的時間複雜度爲：從循環和條件語句計算時間複雜度

= 1 + n *((n * (1 + n * 1)) + (n * 1))) 
= 1 + n * (n * (n + 1) + n) 
= 1 + n * (n^2 + n + n) 
= 1 + n^3 + n^2 + n^2 
= 1 + n^3 + 2 * n^2`

所以它是O(n^3)。

我的計算是否正確？

代碼：

int result = 0 ;    //1 
for (int i = 0 ; i <N ; i++){ //n 
    for (int j = 0 ; j <N ; j++){ //n 

     for (int k = 0 ; k <N ; k++){ //n 

      int x = 0 ; //1 
      while (x < n){ //n 
      result ++ ; //1 
      x+=3 ; //1 
     } 

     } 

     for(int k = 0 ; k<2*M ; K++){ //n 
      if(K%7 == 4) 
       result ++ ; 
     } 

    } 

}

來源

2014-10-12 Yallarace Mohamed

經過快速瀏覽，我猜測複雜性是O（N^4）。我認爲這是一個猜測，因爲提供的代碼有一些拼寫錯誤等，這可能會改變它的含義。我提供以下我的解釋：

int result = 0 ; 
for (int i = 0 ; i <N ; i++) { // N 
    for (int j = 0 ; j <N ; j++) { //N * N 

    for (int k = 0 ; k <N ; k++) { // N*N*N 
     int x = 0 ; //1 
     while (x < N){ //This was x < n, but n was undefined, so assumed N. N^4 
     result ++; 
     x+=3; 
     } 
    } 

    for(int k = 0 ; k<2*N ; k++) { //N*N*(2*N), this was k<2*M, but M was undefined 
     if(k%7 == 4) result++; 
    } 
    } 
}

對，所以你可以看到上面的for循環三層深，從0到迭代，每次N;這可以很容易地看到給我們O（N^3）。然而，我們在最內層也有一個while循環，這個循環也可以用N來表徵 - 特別是N/3 - 這將我們帶到O（N^4）。

來源

2014-10-12 13:46:53 Alan

是的，真棒回答謝謝艾倫，但是當大o會記錄n和我的問題，如果for的第一行是這樣的（int i = 0; i> N; i ++）{// N}和ñ說= 8我的意思是沒有達到循環的條件，所以大o將是O（1） – 2014-10-12 16:25:47

對不起@YallaraceMohamed我不太明白這一點。 O（log n）在哪裏進入？ – Alan 2014-10-13 00:12:41

在這個例子中沒有否問什麼時候的複雜度會是n log n – 2014-10-13 04:11:26

IF的時間複雜度可以表示爲A（N^3）+ B（N^2）+ C（N）+ d，其中a，b，c和d是常數，時間複雜度是O（n^3）。

我猜你是對的。

來源

2014-10-12 13:40:54

從循環和條件語句計算時間複雜度

回答

相關問題