時間代碼的複雜性

Question

很抱歉，如果這個問題是一個重複的，或者是一種愚蠢的，但我真正的新算法開發） 你能解釋我什麼是下面這段代碼的複雜性

for (int i=0; i<n; i++) { 
    for (int j=0; j<i; j++) { 
     do stuff... 
    } 
} 

是這個代碼的複雜性n^2或nlogn？ 謝謝

Answer 1

複雜性是O(n^2)。

對於外部循環的第一次迭代中，內環將迭代0倍

對於外部循環的第二次迭代中，內環將迭代1倍。

對於外循環的第三次迭代，內循環將迭代2次。

.........

對於外環的n次迭代，內環將迭代n - 1倍。

迭代總數= 0 + 1 + 2 + 3 + 4 ...... + (n - 1)

我們知道，等差數列

1 + 2 + 3 + ..... + (n - 2) + (n - 1) + n = (n * (n + 1))/2 

所以，

0 + 1 + 2 + 3 + 4 ...... + (n - 1) 
= (n * (n - 1))/2 
~ n^2 

考慮do stuff階段將在固定時間內執行的總和，整體時間複雜度爲O(n^2)。