气泡排序算法的时间复杂度如何导致O（n ^ 2）的计算方式？

Question

我知道为什么冒泡排序是O（n ^ 2）。

但是在许多解释中，我看到这样的东西：

(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1
Sum = n(n-1)/2

您如何从该部分计算Sum：

(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1

有人可以帮忙吗？

Answer 1

这是诀窍：

If n is even:
  n + (n-1) + (n-2) + … + 3 + 2 + 1
= [n + 1] + [(n-1) + 2] + [(n-2) + 3] + … + [(n - (n/2 - 1)) + n/2]
= (n + 1) + (n + 1) + (n + 1) + … + (n + 1)
= n(n+1)/2

If n is odd:
  n + (n-1) + (n-2) + … + 3 + 2 + 1
= [n + 1] + [(n-1) + 2] + [(n-2) + 3] + … + [(n - (n-1)/2 + 1) + (n-1)/2] + (n-1)/2 + 1
= (n+1) + (n+1) + (n+1) + … + (n+1) + (n-1)/2 + 1
= (n+1)(n-1)/2 + (n-1)/2 + 1
= (n^2 - 1 + n - 1 + 2)/2
= (n^2 + n)/2
= n(n+1)/2

对于您的情况，由于您要计算n-1而不是n，因此在此公式中将n替换为（n-1），然后简化：

   x(x+1)/2, x = (n-1)
=> (n-1)((n-1)+1)/2 
 = (n-1)(n)/2 
 = n(n-1)/2

Answer 2

在不导出方程式的情况下理解的最简单的“证明”是将复杂度想象为面积：

所以，如果我们有序列：

n+(n-1)+(n-2)...

我们可以从中创建形状...让我们考虑n=5：

n     5     *****
n-1   4     ****
n-2   3     ***
n-3   2     **
n-4   1     *

现在，当您查看起点时，它们会形成一个直角三角形，并带有2个等长的边...即n x n正方形的一半，因此面积为：

area = ~ n.n / 2 = (n^2)/2

复杂度中常量是没有意义的，因此复杂度将是：

O(n^2)