爲什麼冒泡排序O（n^2）？

int currentMinIndex = 0; 

for (int front = 0; front < intArray.length; front++) 
{ 
    currentMinIndex = front; 

    for (int i = front; i < intArray.length; i++) 
    { 
     if (intArray[i] < intArray[currentMinIndex]) 
     { 
      currentMinIndex = i; 
     } 
    } 

    int tmp = intArray[front]; 
    intArray[front] = intArray[currentMinIndex]; 
    intArray[currentMinIndex] = tmp; 
}

內循環迭代：n +（n-1）+（n-2）+（n-3）+ ... + 1次。爲什麼冒泡排序O（n^2）？

外循環迭代：n次。

所以，你得到N *

是不是N *（N *（N + 1）/ 2）（數字1到n的總和）= N *（（N^2）+ n/2）

這將是（n^3）+（n^2）/ 2 = O（n^3）？

我很積極我做錯了。爲什麼不是O（n^3）？

來源

2012-07-13 ordinary

你正在計算外'n'兩次。你的內部循環本身是O（n）。 – 2012-07-13 20:20:40

不要挑剔，但你顯示的算法是[選擇排序]（http://en.wikipedia.org/wiki/Selection_sort）不是[泡泡排序]（http://en.wikipedia.org/wiki/Bubble_sort ） – 2012-07-13 20:33:16

上週，我寫了一篇關於漸近複雜性的文章，巧合之處在於，我以泡泡排序爲例。給它一個鏡頭:-)（http://en.algoritmy.net/article/44682/Asymptotic-complexity）。正如亨克所說的那樣，你的錯誤是內層循環是O（n）。 O（n^2） - 算術順序的總和是兩個循環的複雜度。 – malejpavouk 2012-07-13 20:39:14

你是對的，外層循環重複n次，內層循環重複n次，但是你重複計算工作。如果通過總結頂層循環的每次迭代所完成的工作來完成所做的全部工作，則會得到第一次迭代不起作用，第二次迭代n - 1，第三次n - 2等，因爲第i次頂層循環迭代具有內循環n - i的工作。

或者，您可以通過將內部循環完成的工作量乘以循環運行的總次數來完成所做的工作。內部循環在每次迭代中都運行O（n），並且外部循環運行O（n）次迭代，所以總的工作是O（n ）。

您試圖將這兩種策略結合在一起發生錯誤。確實外環是第一次工作，然後是n - 1，然後是n - 2等等。但是，您不會將此工作乘以n來獲得總和。這將每次迭代計數n次。相反，你可以將它們彙總在一起。

希望這會有所幫助！

來源

2012-07-13 20:19:41 templatetypedef

非常感謝。我明白我現在做錯了什麼 – ordinary 2012-07-13 20:27:04

可能值得補充的是，大O描述了與輸入大小成比例的算法的_growth比率，它不一定與算法運行的確切迭代量相同。 – 2012-07-13 20:29:57

BubbleSort完成（n-1）*（n-1）次迭代會準確嗎？因此N^2次迭代。這是時間複雜性。我是否正確地承擔這一點？ – user3396486 2015-12-11 22:26:40

內循環迭代n次（在最壞的情況下）：

for(int i = front; i < intArray.length; i++)

外環迭代n次：

for(int front = 0; front < intArray.length; front++)

因此爲O（n^2）

來源

2012-07-13 20:20:18 NominSim

你的內正如你所說的n +（n-1）+（n-2）+（n-3）+ ... + 1次，循環迭代IN TOTAL。所以它是O（n +（n-1）+（n-2）+（n-3）+ ... + 1）= O（n（n + 1）/ 2）= O（n^2）

來源

2012-07-13 20:20:57 GL770

啊，剛剛有阿哈的時刻。 TY。 – ordinary 2012-07-13 20:25:29

n = 5求解（n *（n + 1））/ 2，得到15，而不是5^2 = 25。不一樣。 – ruralcoder 2013-01-25 06:35:48

你如何基本上計算出n ...

每一行：+1
每個迴路* N

於是你開始添加號碼來獲得你的第一個循環，現在你有N + 1，你繼續前進，最終得到N * N或N^2的時間加上一些數字。拉出數字，因爲它通常與N相比是微不足道的。

非常多N是循環中所有項目的表示，類似1,2,3 ... N。所以它只是代表一個數字，而不是一個循環多少次循環。

來源

2012-07-13 20:21:44

-1

只是爲了有一些Python版本的冒泡排序...

def bubble_sort(input): 
    n = len(input) 
    iterations = 0 
    for i in xrange(n, 1, -1): 
     for j in range(0, i - 1): 
      iterations += 1 
      if input[j] > input[j+1]: 
       input[j],input[j+1] = input[j+1],input[j] 

    print iterations 
    return input

迭代已添加到內部循環來計算總迭代次數。與泡沫排序無關。

傳遞5個元素的數組，導致15次迭代不是25次。另外，當預先排序時，它也會導致15次迭代。但複雜性也必須考慮到比較和交換。

來源

2013-01-25 06:30:53 ruralcoder

k=1(sigma k)n = n(n+1)/2 
because: 
    s = 1 + 2 + ... + (n-1) + n 
    s = n + (n-1) + ... + 2  + 1 
+) 
=================================== 
    2s = n*(n+1) 
    s = n(n+1)/2 
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1 
, k=0(sigma k)n-1 equals [k=1(sigma k)n] - n 
therefore, n(n+1)/2 - n = n(n-1)/2 
which is 1/2(n^2-n) => O(1/2(n^2-n)) 
in big O notation, we remove constant, so 
O(n^2-n) 
n^2 is larger than n 
O(n^2)

來源

2015-01-24 02:52:16 winuxguy

爲什麼冒泡排序O（n^2）？

回答

相關問題