time-complexity - 如何分析给定优化冒泡排序的复杂性？

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))。

顺便说一句，优化冒泡排序的实现包含一个错误：第if9 行应该在外部循环内部，但在内部循环外部。