如何分析給定優化氣泡排序的複雜性？

Question

這是一個優化的氣泡排序算法的僞代碼。我試圖分析它的時間複雜性，但我不確定第4行（如果A [i-1]> A [i]）的成本是多少。答案是（n-1）+（n-2）+ ........ + 1？第5至8行的成本又是多少？

1.for j = A.length to 2 
2. swapped = false 
3. for i = 2 to j 
4.  if A[i-1] > A[i] 
5.   temp = A[i] 
6.   A[i-1] = A[i] 
7.   A[i-1] = temp 
8.   swapped = true 
9. if(!swapped) 
10.  break 

Answer 1

單次迭代的第5到第8行的代價是O（1）。

第3-8行的循環成本爲O（j-1）。在最壞的情況下，整個的成本是O（（n-1）+（n-2）+ ... + 2）= O（n^2）（當然在最好的情況下，當數組已經排序後，成本將只有O（n-1））。

順便說一下，您的優化氣泡排序的實現包含一個錯誤：第9行的if應位於外部循環內部，但在內部之外。