這個氣泡排序函數的時間複雜度是多少？

我寫了這個氣泡排序函數，但我很難搞清楚它的時間複雜度。這個氣泡排序函數的時間複雜度是多少？

function bubbleSort(items) { 
    for (var i = items.length; i > 0; i--) { 
     for (var j = 0; j < i; j++) { 
     if (items[j] > items[j + 1]) { 
      var temp = items[j]; 
      items[j] = items[j + 1]; 
      items[j + 1] = temp; 
     } 
     } 
    } 

    return items; 
}

我知道外環的時間複雜度爲O（n）。但是內部循環的時間複雜度是多少（因爲它在每次傳遞中通過一個更少的元素items）？

來源

2017-01-22 georgej

谷歌爲「冒泡排序複雜性」，以找到[維基百科]（https://en.wikipedia.org/wiki/Bubble_sort#Performance）這樣的參考。或者在搜索結果中找到375條結果。 –

內部循環是O（n）。開始時它會執行n次，最後1次。平均而言，它將執行n/2次。常數因子不重要，所以這就是O（n）。

總的來說，整體運行時間因此是O（n ）。

來源

2017-01-22 04:48:58

如果考慮內循環多少次運行，你可能有一個更好的主意：

1st run : N times, 
2nd run: N-1 times 
... 
Nth run: 1 time.

如果添加他們都

N + (N-1) + (N-2) + ... + 1 = [N * (N+1)]/2

倍。這使得O（N^2）。欲瞭解更多信息，點擊此處查看這樣的回答：https://stackoverflow.com/a/29556003

來源

2017-01-22 05:04:10

我不明白。如果這個問題/答案提供了「更多信息」，那麼這個問題是不是重複？ –

@torazaburo你是對的，因爲我找不到從移動應用程序「標記爲重複」選項，我把答案的URL放在下面。感謝提示btw。 –

一種方法來計算你的算法的時間複雜度需要注意的是內循環執行i迭代，其中來自ni範圍下降到1（其中n是的長度輸入）。這意味着，我們可以做一個總結，以獲得在算法的步驟總數：

n + (n-1) + ... + 3 + 2 + 1

該總和有一個熟悉的封閉的公式：

n*(n+1)/2

這個公式顯然是O(n^2)。

來源

2017-01-22 05:13:44

這個氣泡排序函數的時間複雜度是多少？

回答

相關問題