冒泡排序算法求时间复杂度

Question

我正在尝试找出冒泡排序的时间复杂度

n=length[A]
for j <- n-1 to 1
for i <- 0 to j-1
if A[i]>a[i+1]
temp=A[i]
A[i]=A[i+1]
A[i+1]=temp

return A

请哪位大侠帮忙谢谢

Answer 1

在第 1 行中，我们将数组的长度分配给 n 所以常数时间
在第 2 行中，我们有一个 for 循环，每次迭代都将 j 递减 1，直到 j=1，总共将迭代 n-2 次。
在第一个 for 循环中，我们有第二个 for 循环，每次迭代都会将 i 递增 1，直到 i=j-1 并将迭代 j-1 次。在内部 for 循环的每次迭代中，我们都有第 4、5、6、7 行，它们都只是赋值和数组访问，总共花费了常数时间。
我们可以这样理解这两个for循环：外层for循环每迭代一次，内层for循环就会迭代j-1次。
因此，在外层 for 循环的第一次迭代中，我们有 j = n-1。这意味着内部 for 循环将迭代 (n-1)-1 = (n-2) 次。然后在外部 for 循环的第二次迭代中，我们有 j= n-2 因此内部 for 循环将迭代 (n-2)-1 = (n-3) 次，依此类推。我们这样做直到 j = 1。
然后我们将得到等式：(n-2) + (n-3) + ... + 2 + 1 这是整个算法执行后内循环将迭代的总次数。我们知道 1 + 2 + ... + n-1 + n = n(n-1)/2 所以我们的表达式可以简化为： n(n-1)/2 -(n-1) -n = n(n-1)/2 -2n + 1 = O(n^2).
由于我们的内部 for 循环将迭代 O(n^2) 次，并且在每次迭代中做恒定的工作，那么这意味着我们的运行时间将为 O(cn^2)，其中 c 是完成的恒定工作量通过第 4、5、6、7 行。将 O(cn^2) 与第 1 行 O(1) 相结合，我们得到 O(cn^2) + O(1)，即 O(n^2).
因此 BubbleSort 的运行时间是 O(n^2)。

如果您仍然感到困惑，那么也许这会对您有所帮助：https://www.youtube.com/watch?v=Jdtq5uKz-w4

bubble sort algorithm find time complexity