我囉嗦兩句,從頭講起。氣泡排序是一種用時間換空間的排序方法,最壞情況是把順序的排列變成逆序,或者把逆序的數列變成順序。在這種情況下,每一次比較都需要進行交換運算。舉個例子來說,一個數列 5 4 3 2 1 進行冒泡升序排列,第一次大迴圈從第一個數(5)開始到倒數第二個數(2)結束,比較過程:先比較5和4,4比5小,交換位置變成4 5 3 2 1;比較5和3,3比5小,交換位置變成4 3 5 2 1……最後比較5和1,1比5小,交換位置變成4 3 2 1 5。這時候共進行了4次比較交換運算,最後1個數變成了數列最大數。第二次大迴圈從第一個數(4)開始到倒數第三個數(2)結束。進行3次比較交換運算。……所以總的比較次數為 4 + 3 + 2 + 1 = 10次對於n位的數列則有比較次數為 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2,這就得到了最大的比較次數而O(N^2)表示的是複雜度的數量級。舉個例子來說,如果n = 10000,那麼 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2,相對10^8來說,10000小的可以忽略不計了,所以總計算次數約為0.5 * N^2。用O(N^2)就表示了其數量級(忽略前面係數0.5)。打了那麼多字應該解釋的比較清楚了吧,什麼地方看不明白再問吧
我囉嗦兩句,從頭講起。氣泡排序是一種用時間換空間的排序方法,最壞情況是把順序的排列變成逆序,或者把逆序的數列變成順序。在這種情況下,每一次比較都需要進行交換運算。舉個例子來說,一個數列 5 4 3 2 1 進行冒泡升序排列,第一次大迴圈從第一個數(5)開始到倒數第二個數(2)結束,比較過程:先比較5和4,4比5小,交換位置變成4 5 3 2 1;比較5和3,3比5小,交換位置變成4 3 5 2 1……最後比較5和1,1比5小,交換位置變成4 3 2 1 5。這時候共進行了4次比較交換運算,最後1個數變成了數列最大數。第二次大迴圈從第一個數(4)開始到倒數第三個數(2)結束。進行3次比較交換運算。……所以總的比較次數為 4 + 3 + 2 + 1 = 10次對於n位的數列則有比較次數為 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2,這就得到了最大的比較次數而O(N^2)表示的是複雜度的數量級。舉個例子來說,如果n = 10000,那麼 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2,相對10^8來說,10000小的可以忽略不計了,所以總計算次數約為0.5 * N^2。用O(N^2)就表示了其數量級(忽略前面係數0.5)。打了那麼多字應該解釋的比較清楚了吧,什麼地方看不明白再問吧