algorithm - 分析简单的冒泡排序循环(最坏情况)

Question

我得到了一个简单的伪代码算法:

for j=1 to A.length-1 //first line 
  for i =1 to A.length-j //second line 
    if A[i-1] >A[i]
      swap A[i-1] and A[i]

有人告诉我第二行是这样运行的(最坏情况:

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

我理解当第一行运行时，第二个循环运行n次，每次下一次迭代j，第二个循环少运行1次(n-1) +(n-2) ETC。 我明白这显然是一个总结，但我不明白为什么最后添加的是 2(对于第二行)。

如有任何意见，我们将不胜感激。

Answer 1

考虑到 A.length 为 n，您可以清楚地验证相同。我正在为你做这件事:

for j=1 to n-1 //first line 
  for i =1 to n-j //second line 
    if A[i-1] >A[i]
     swap A[i-1] and A[i]

因此，对于第 j = 1 处的外循环的第一次迭代，内循环运行了 1 到 n-1 次。 => n-1

对于外循环的第二次迭代，内循环运行1到n-2次。 => n-2

对于第i次外层循环，内层循环会运行1到n-i次，=> n-i。

外循环的最后一次迭代将在 j = n-1 时进行，内循环将运行 i = 1 到 n-(n - 1) = 1 次。

因此，结果将是 n-1 + n-2 + ... + 1 = (n-1)*n/2 的总和。

所以，显然最后应该是1。

I understand that it's clearly a summation, here but what I don't get is why the last thing added is 2 (FOR THE SECOND LINE).

我建议您与您的 friend /教授讨论此事，显然，他错误地告知了您。这就是我在这里解决的问题。

人们通常认为，当数组的前 n-1 个元素已经排序后，最后一个元素已经适合确切的位置。因此，他们通常会这样假设并离开最后一步。

但是，在计算 OR 算法中，我们(通常)计算这个。您的这段代码正在此处计算。