19 
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)？

4

6 回答 6

22

你是正确的，外循环迭代 n 次，内循环也迭代 n 次，但是你重复计算了工作。如果您通过将顶层循环的每次迭代完成的工作相加来计算完成的总工作量，您会得到第一次迭代没有工作 n 工作，第二次工作 n - 1，第三次工作 n - 2 等等，因为第 i顶层循环的迭代让内部循环n - i工作。

或者，您可以通过将完成的工作量乘以内部循环乘以循环运行的总次数来计算完成的工作。内部循环在每次迭代中运行 O(n) 次，外部循环运行 O(n) 次迭代，因此总工作量为 O(n 2 )。

尝试将这两种策略结合起来是错误的。确实，外部循环第一次工作 n，然后是 n - 1，然后是 n - 2，等等。但是，您不要将此工作乘以 n 来获得总数。这将计算每次迭代 n 次。相反，您可以将它们加在一起。

希望这可以帮助！

于 2012-07-13T20:19:41.237 回答
9

正如您所说的 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)

于 2012-07-13T20:20:57.393 回答
2

内部循环迭代 n 次（在最坏的情况下）：

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

外循环迭代 n 次：

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

因此 O(n^2)

于 2012-07-13T20:20:18.630 回答
1 
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)
于 2015-01-24T02:52:16.460 回答
1

你基本上如何计算N ...

  • 每行：+1

  • 每个循环 *N

    所以你开始添加数字到你的第一个循环，现在你有 N+1，你继续前进，你最终得到 N*N 或 N^2 时间加上一些数字。拉出这个数字，因为它与 N 相比通常是微不足道的。

N 几乎是循环中所有项目的表示，类似于 1,2,3...N。所以它只是代表一个数字而不是循环多少次。

于 2012-07-13T20:21:44.027 回答
0

这是另一个加速冒泡排序的版本，当我们只使用一个交换变量来提前终止第一个 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();
}
于 2019-03-05T06:46:20.240 回答