为什么冒泡排序的时间复杂度是O(n^2)？

Question

for (int front = 1; front < intArray.length; front++)
{
    for (int i = 0; i  < intArray.length - front; i++)
    {
        if (intArray[i] > intArray[i + 1])
        {
            int temp = intArray[i];
            intArray[i] = intArray[i + 1];
            intArray[i + 1] = temp;
        }
    }
}

内部循环正在迭代：n + (n-1) + (n-2) + (n-3) + ... + 1 次。

外部循环正在迭代：n 次。

因此，您将得到 n *（1到n的数字之和）

难道不是 n *（n *（n + 1）/ 2）= n *（（n ^ 2）+ n / 2）

这将是（n ^ 3）+（n ^ 2）/ 2 = O（n ^ 3）吗？

我确定我做错了。 为什么不是 O(n^3)？

- ordinary

---

你在两次计算外部的 n。你的内部循环本身是 O(n)。 - H H

不是挑剔，但你展示的算法是一种选择排序（Selection sort），而不是冒泡排序（Bubble sort）。 - Frank Boyne

上周，我写了一篇关于渐近复杂度的文章，巧合的是，我用冒泡排序作为例子。你也可以试试 :-)（http://en.algoritmy.net/article/44682/Asymptotic-complexity）。你的错误就像Henk所说的那样，内部循环是O(n)。O(n^2) - 算术序列的总和是两个循环的复杂度。 - malejpavouk

我同意，这不是冒泡排序。 - whamsicore

添加注释是因为这里展示的算法经过编辑后就是冒泡排序。我读了评论感到困惑，但现在相信已经解决了。 - Switch386

Answer 1

您是正确的，外层循环执行n次，内层循环也执行n次，但您重复计算了工作量。如果您通过总结顶级循环的每个迭代中完成的工作来计算总工作量，您会发现第一次迭代完成n个单位的工作，第二次完成n-1，第三次完成n-2，以此类推，因为顶级循环的第i次迭代使内层循环完成n-i个单位的工作。

或者，您可以将内层循环完成的工作量乘以该循环运行的总次数来计算工作量。内层循环在每次迭代中都要做O(n)的工作，而外层循环运行O(n)次，所以总工作量为O(n²)。

您试图将这两种策略合并是错误的。确实，外层循环第一次执行n个单位的工作，然后n-1，然后n-2等等。但是，您不应该将这个工作乘以n以获取总工作量。这将使每个迭代计数n次。相反，您只需要将它们相加即可。

希望这有所帮助！

- templatetypedef

---

值得一提的是，大O表示算法与输入大小成比例的增长速率，这并不一定等同于算法运行所需的确切迭代次数。 - user849425

可以说冒泡排序完成了(n-1)*(n-1)次迭代，因此总共进行了N^2次迭代。这就是时间复杂度。我在假设上是正确的吗？ - Tiny

冒泡排序不执行(n-1)*(n-1)， 它执行外循环(n-1)：内循环[(n-1),(n-2),(n-3),...,(2),(1)] 因此，您可以说冒泡排序迭代内部循环[(n-1),(n-2),(n-3),...,(2),(1)]次。 这是n(n-1)/2次，而不是N^2次， 但正如用户“user849425”在上面的评论中建议的那样，大O并不是迭代次数。 - Pankaj

大O符号太令人困惑了。 内部循环的时间复杂度是O(n-i)，而不是O(n)。 - Pankaj

Answer 2

您的内部循环在总共迭代n + (n-1) + (n-2) + (n-3) + ... + 1次。因此它的时间复杂度为O(n + (n-1) + (n-2) + (n-3) + ... + 1) = O(n(n+1)/2) = O(n^2)。

- GL770

---

啊，我刚刚有了“啊哈”时刻。谢谢。 - ordinary

将(n*(n+1))/2代入n=5计算，答案为15，而不是5的平方25。两者不同。 - ruralcoder

那我可以把它写成O((n*(n+1))/2)和O(n^2)吗？ - Aniket Kariya

Answer 3

k=1(sigma k)n = n(n+1)/2
because:
  s = 1 +  2    + ... + (n-1) + n
  s = n + (n-1) + ... + 2     + 1
+)
===================================
  2s = n*(n+1)
   s = n(n+1)/2
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1
, k=0(sigma k)n-1 equals [k=1(sigma k)n] - n
therefore, n(n+1)/2 - n = n(n-1)/2
which is 1/2(n^2-n) => O(1/2(n^2-n))
in big O notation, we remove constant, so
O(n^2-n)
n^2 is larger than n
O(n^2)

- winuxguy

---

最好的解释。 - CoderCat

Answer 4

内部循环最坏情况下迭代n次：

for(int i = front; i < intArray.length; i++)

外层循环迭代n次：

for(int front = 0; front < intArray.length; front++)

因此O(n^2)

- NominSim

Answer 5

如何基本计算N...

• 每一行：+1

• 每个循环 * N

  所以当你开始添加数字时，到达第一个循环，现在你有N+1，继续进行，最终得到N*N或N^2的时间加上一些数。将该数字减去，因为与N相比通常不重要。

基本上，N是循环中所有项的表示方式，就像1、2、3...N一样。因此，它只是表示一个数字，而不是循环执行的次数。

- Travis Pessetto

Answer 6

这是另一个版本，用于加速冒泡排序。我们仅使用一个变量swapped来提前终止第一个for循环。这将使时间复杂度更好。

#include <stdio.h>
#include <stdbool.h>
#define MAX 10

int list[MAX] = {1,8,4,6,0,3,5,2,7,9};

void display(){
   int i;
   printf("[");

   for(i = 0; i < MAX; i++){
      printf("%d ",list[i]);
   }

   printf("]\n");
}

void bubbleSort() {
   int temp;
   int i,j;

   bool swapped = false;       

   // 1st loop
   for(i = 0; i < MAX-1; i++) { 
      swapped = false;

      // 2nd loop
      for(j = 0; j < MAX-1-i; j++) {
         printf("     Compare: [ %d, %d ] ", list[j],list[j+1]);

         if(list[j] > list[j+1]) {
            temp = list[j];
            list[j] = list[j+1];
            list[j+1] = temp;

            swapped = true;
         }

      }

      if(!swapped) {
         break;
      }

      printf("Loop number %d#: ",(i+1)); 
      display();                     
   }

}

main(){
   printf("Before: ");
   display();
   printf("\n");

   bubbleSort();
   printf("\nAfter: ");
   display();
}

- Giang Nguyen