为什么冒泡排序O（n^2）？

int currentMinIndex = 0; 

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

    for (int i = front; i < intArray.length; i++) 
    { 
     if (intArray[i] < intArray[currentMinIndex]) 
     { 
      currentMinIndex = i; 
     } 
    } 

    int tmp = intArray[front]; 
    intArray[front] = intArray[currentMinIndex]; 
    intArray[currentMinIndex] = tmp; 
}

内循环迭代：n +（n-1）+（n-2）+（n-3）+ ... + 1次。为什么冒泡排序O（n^2）？

外循环迭代：n次。

所以，你得到N *

是不是N *（N *（N + 1）/ 2）（数字1到n的总和）= N *（（N^2）+ n/2）

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

我很积极我做错了。为什么不是O（n^3）？

来源

2012-07-13 ordinary

你正在计算外'n'两次。你的内部循环本身是O（n）。 – 2012-07-13 20:20:40

不要挑剔，但你显示的算法是[选择排序]（http://en.wikipedia.org/wiki/Selection_sort）不是[泡泡排序]（http://en.wikipedia.org/wiki/Bubble_sort ） – 2012-07-13 20:33:16

上周，我写了一篇关于渐近复杂性的文章，巧合之处在于，我以泡泡排序为例。给它一个镜头:-)（http://en.algoritmy.net/article/44682/Asymptotic-complexity）。正如亨克所说的那样，你的错误是内层循环是O（n）。 O（n^2） - 算术顺序的总和是两个循环的复杂度。 – malejpavouk 2012-07-13 20:39:14

你是对的，外层循环重复n次，内层循环重复n次，但是你重复计算工作。如果通过总结顶层循环的每次迭代所完成的工作来完成所做的全部工作，则会得到第一次迭代不起作用，第二次迭代n - 1，第三次n - 2等，因为第i次顶层循环迭代具有内循环n - i的工作。

或者，您可以通过将内部循环完成的工作量乘以循环运行的总次数来完成所做的工作。内部循环在每次迭代中都运行O（n），并且外部循环运行O（n）次迭代，所以总的工作是O（n ）。

您试图将这两种策略结合在一起发生错误。确实外环是第一次工作，然后是n - 1，然后是n - 2等等。但是，您不会将此工作乘以n来获得总和。这将每次迭代计数n次。相反，你可以将它们汇总在一起。

希望这会有所帮助！

来源

2012-07-13 20:19:41 templatetypedef

非常感谢。我明白我现在做错了什么 – ordinary 2012-07-13 20:27:04

可能值得补充的是，大O描述了与输入大小成比例的算法的_growth比率，它不一定与算法运行的确切迭代量相同。 – 2012-07-13 20:29:57

BubbleSort完成（n-1）*（n-1）次迭代会准确吗？因此N^2次迭代。这是时间复杂性。我是否正确地承担这一点？ – user3396486 2015-12-11 22:26:40

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

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

外环迭代n次：

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

因此为O（n^2）

来源

2012-07-13 20:20:18 NominSim

你的内正如你所说的n +（n-1）+（n-2）+（n-3）+ ... + 1次，循环迭代IN TOTAL。所以它是O（n +（n-1）+（n-2）+（n-3）+ ... + 1）= O（n（n + 1）/ 2）= O（n^2）

来源

2012-07-13 20:20:57 GL770

啊，刚刚有阿哈的时刻。 TY。 – ordinary 2012-07-13 20:25:29

n = 5求解（n *（n + 1））/ 2，得到15，而不是5^2 = 25。不一样。 – ruralcoder 2013-01-25 06:35:48

你如何基本上计算出n ...

每一行：+1
每个回路* N

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

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

来源

2012-07-13 20:21:44

-1

只是为了有一些Python版本的冒泡排序...

def bubble_sort(input): 
    n = len(input) 
    iterations = 0 
    for i in xrange(n, 1, -1): 
     for j in range(0, i - 1): 
      iterations += 1 
      if input[j] > input[j+1]: 
       input[j],input[j+1] = input[j+1],input[j] 

    print iterations 
    return input

迭代已添加到内部循环来计算总迭代次数。与泡沫排序无关。

传递5个元素的数组，导致15次迭代不是25次。另外，当预先排序时，它也会导致15次迭代。但复杂性也必须考虑到比较和交换。

来源

2013-01-25 06:30:53 ruralcoder

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-24 02:52:16 winuxguy

为什么冒泡排序O（n^2）？

回答

相关问题