如何分析给定优化气泡排序的复杂性？

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应位于外部循环内部，但在内部之外。