什麼是嵌套循環的Big-Oh i = 0..n-2，j = i + 1..n-1？

Question

考慮下面的代碼：

for (int i = 0; i < n-1; ++i) 
{ 
    for (int j = i+1; j < n; ++j) 
    { 
     // Do work. 
    } 
} 

什麼是它的大哦值（超過n）？我想這是O（N^2），但我不確定。

我在這裏找到一個類似的問題：complexity for nested loops

，但它並不完全，我認爲是相同的。

Answer 1

是的，那是O(N^2)。配對內循環迭代的開始，並在外環的結尾，就像這樣：

內循環將執行...

• N-1倍於外的第一次迭代環，並1時間上最後迭代
• N-2在外迴路的第二迭代次數，以及在第二次2倒數在外循環的第三次迭代的迭代
• N-3次，3次，第三次到最後一次迭代
• ...等等;你會有這樣的N/2對;當N是奇數時，最後一對是不完整的。

可以看到，每一對執行共N次，你有這樣的N/2對，共N*(N-1)/2倍。

該公式的推導方式來自於derivation of the formula for the sum of arithmetic progression，其公共差異爲1。

Answer 2

應該可以這樣檢查它。

int z = 0, n = 10; // try 20 etc 
for (int i = 0; i < n-1; ++i) 
{ 
    for (int j = i+1; j < n; ++j) 
    { 
     z++; 
    } 
} 

現在檢查z的值。

With n = 10; z becomes 45 
With n = 20; z becomes 190 
With n = 40; z becomes 780 

在Ñ翻倍引起Ž成爲〜4倍其值。因此，它大約是O(n^2)。

Answer 3

有條不紊，適馬符號（經驗證實），就可以得到迭代的確切數目加上增長的複雜性順序：