三個for循環的大O表示法

-1

以下代碼的複雜程度如何？它會是N^2 * log（n）？三個for循環的大O表示法

for (int m = 1; m <= n; m++) 
{ 
    for (int k = m; k >= 1; k--) 
    { 
     for (int i = 1; i <= k; i++) 
     { 
      //do something here 
     } 
    } 
}

任何幫助表示讚賞謝謝。

來源

2014-11-23 ralis

爲什麼認爲這將是'N R個2log（N）'？ – mkobit 2014-11-23 22:36:39

@ralis - 正確的方法是**分析代碼而不是猜測。（答案是「不，不是」）。 – 2014-11-23 22:49:52

@ Stephen C-你是什麼意思？ – ralis 2014-11-23 22:54:30

多久最內層循環採取給出的循環體的運行時間是O(C)？ O(C*k)

第二次循環需要多長時間？ O(C*(1+2+3+...+m)) = O(C*m²)

整個代碼snipplet需要多長時間？ O(C*(1²+2²+3²+...+n²)) = O(C*n³)

對於求和多項式見Faulhaber's formula。

來源

2014-11-23 23:01:45 fabian

你是如何得到'O（C *（1²+2²+3²+ ... +n²））'？實際迭代次數爲1 +（1 + 2）+（1 + 2 + 3）+ ...（1 + 2 + 3 + ... + n） n *（n + 1））/ 2。你是建議前者是一個確切的數字，還是僅僅將它用作實際數量的一個鬆散上限？ – 2014-11-24 14:08:09

@AndyThomas：由於O符號，確切的計數在這裏是不相關的。我並不是說這是一個確切的數字，但是低於2的電力可以安全地忽略。（Faulhaber的公式告訴你，任何一個'x'次多項式的和導致'x + 1'次多項式） – fabian 2014-11-24 14:27:35

第一個循環執行n次。第二個循環執行n/2次。第三個循環執行k/2次，這等於n/4次。

這給你一個O（n^3）的複雜度。

實證檢驗：

#include <iostream> 

using namespace std; 

int main() { 
    int n = 1000; 

    long first = 0, second = 0, third = 0; 

    for (int m = 1; m <= n; m++) 
    { 
     first++; 
     for (int k = m; k >= 1; k--) 
     { 

      second++; 
      for (int i = 1; i <= k; i++) 
      { 
       third++; 
      } 
     } 
    } 

    cout << first << " " << second << " " << third << endl; 

    return 0; 
}

結果：

1000 500500 167167000

來源

2014-11-23 22:45:19 Aleksandar

我認爲你誤算了第二和第三個循環的迭代次數。 – 2014-11-23 22:51:27

如果使用六西格瑪符號，你能想出以下：

enter image description here

來源

2014-11-25 06:25:56

三個for循環的大O表示法

回答

相關問題