Bubble-sort算法的分析

Question

通常，buublesort的運行時間複雜度爲O（n^2），但下面給出的算法有一個while循環和for循環for循環取決於n，但while循環只是簡單的一個布爾值的檢查器。任何人都可以告訴我如何計算此算法的運行時間？

bool done; 
done = false; 
while (! done) 
{ 
done = true; 
for (i = 0 ; i < a.length-1 ; i ++) 
    { 
    if (a[i] > a[i+1]) 
    { 

// Swap a[i] and a[i+1] 

    temp = a[i]; 
    a[i] = a[i+1]; 
    a[i+1] = temp; 

    done = false; 
    } 
} 
} 

Answer 1

這種情況比具有兩個for循環的算法要困難得多，因爲外循環的確切迭代次數不取決於N，而是取決於數據的特定排列。

如果數組最初被排序，則根本不會進行交換，並且外循環將只運行一次，複雜度爲O(N)。

如果數組最初被反向排序，則每次比較都會導致交換，並且執行外部迴路N次，總複雜度爲O(N²)。

一般情況下更難以評估，因爲它取決於替換元素的數量。人們可以顯示（通過一個不平凡的數學論證），對於隨機無序的數組，平均複雜性仍然是O(N²)。

Answer 2

複雜算法的是在其運行時間的最壞情況（用「的情況下」我的意思的輸入數據的長度增加了整個無限序列）。很明顯，bubblesort只需要O（n）操作「排序」已經排序的數組。但那不算數。有一些陣列（實際上是陣列的序列），它們需要O（n^2）操作。

P.S.有時候，算法是否爲通常在O（n）等中起作用會更有趣。但即使「平均預期時間」是O（0.5 * n^2），它仍然與O（n^2）相同。

Answer 3

如何計算算法的複雜性有幾種方法。最簡單而不是最嚴格的是找到最壞的情況並計算它的週期數/迭代次數。

如果源數組是反之亦然，你的代碼將不得不完成n^2比較。

所有更好的方法都需要一些認真的數學知識：你必須做一些嚴格的證明。例如，證明所選案例確實是最差的案例。