大O：如何確定for循環增量基於outer for循環的運行時？

我有以下算法，運行時複雜度爲O（N^2），但我希望對其有更深入的瞭解，而不是僅記住常見運行時。大O：如何確定for循環增量基於outer for循環的運行時？

什麼是正確的方法來分解它，並分析它與i+1在考慮到內部的for循環？

void printunorderedPairs(int[] array) { 
    for(int i=0; i<array.length; i++) { 
     for(int j=i+1; j<array.length; j++) { 
      System.out.println(array[i] + "," + array[j]); 
     } 
    } 
}

編輯

問計如何分析一個具體的問題

來源

2016-12-31 Jo Ko

可能重複[大O，你如何計算/近似它？]（http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it） –

什麼是正確的方法進行分解和分析

拿鉛筆和紙，並放下一些循環：

現在

 i  inner loops per i 
------------------------------- 
    1    length - 1 
    2    length - 2 
    ..      .. 
    k    length - k 
    ..      .. 
length - 1     1 
length      0

，以獲得所需的總時間，讓我們總結的內循環：

(length - 1) + (length - 2) + ... + (length - k) ... + 1 + 0

這是一個等差數列，其和爲

((length - 1) + 0)/2 * length == length**2/2 - length/2 = O(length**2)

來源

2016-12-31 11:10:27

謝謝你的迴應。只是幾個問題。對於每個我的內部循環，爲什麼它的長度爲1，長度爲2 ... 0？它不應該是我+ 1嗎？你怎麼得出這是一個算術級數？最後，**是什麼意思？ –

@Jo Ko：既然你*從'i + 1'開始*你有'Length - i - 1'來循環*，我們會計算循環，而不是開始索引。 '**'是* power *的常用符號（它來自古老的Fortran），例如'10 ** 3'（十進制爲3d的功能）是'1000'。要查看算術級數，只需放下更多項目：「長度-1，長度-2，長度-3，...，長度-k，... 5,4,3,2,1'。如果你想*證明*，請使用*感應* –

長度 - 我 - 1？它不應該是array.length-1，然後像長度 - 1，長度 - 2，長度 - 3？ –

讓T =的內部循環運行的次數。

半個月左右的時間，當i<array.length/2，它運行至少array.length/2倍。因此，對於大約array.length/2外的迭代中，內循環運行至少array.length/2倍，因此：

T >= (N/2)*(N/2) 
i.e., 
T >= N²/4

這是O（N²）。此外，雖然對於所有 array.length外迭代，內循環運行最多 array.length倍，因此：

T <= N*N, i.e., 
T <= N²

這也是O（N²）。由於我們的時間上限和下限均爲O（N²），我們知道T在O（N²）中。

注意：從技術上講，我們只需要上限來證明T在O（N²）中，但我們通常會尋找儘可能緊的邊界。 T實際上是Ө（N²）。

還需要注意的是：上面使用的一半沒有什麼特別 - 任何常數比例都可以。這些都是一般規則在起作用：

下界：如果你這樣做至少Ω（N）至少工作Ω（N）次，你正在做的Ω（N²）工作。 Ω（N）*Ω（N）=Ω（N²）
上的約束：如果你最多O（N）最多O（N）次的工作，你正在做O（N²）工作。O（N）* O（N）= O（N²）
而且，由於我們有兩個，我們可以使用：Ω（N²）∩O（N²）=Ө（N²）

來源

2016-12-31 18:47:59

最後注意「O （N）* O（N）= O（N 2）「在技術上是濫用符號，因爲O（...）是一組函數。如果你說「f（N）∈O（N），g（N）∈O（N）=> f（N）* g（N）∈O（N 2）」這樣的話，你的教授可能會更喜歡「 –

」 j第一次運行N-1步，第二次運行的是N-2步。然後N-3步。怎麼會這樣？那怎麼能等於1 + 2 + 3 + ... + N-1？ –

@JoKo，我沒有使用很多=標誌。它運行> = N/2步N/2次（然後小於其他N/2次）。它也全部N次運行<= N步。爲了獲得複雜性，您無需計算其運行的確切次數。 –

大O：如何確定for循環增量基於outer for循環的運行時？

回答

相關問題