为什么会冒泡排序为O（n ^ 2）？ [英] Why is bubble sort 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次

The inner loop is iterating: n + (n-1) + (n-2) + (n-3) + ... + 1 times.

外循环迭代：n次

所以，你得到N *（数字1到n的总和）

So you get n * (the sum of the numbers 1 to n)

这不就是N *（N *（N + 1）/ 2）= N *（（N ^ 2）+ N / 2）

Isn't that n * ( n*(n+1)/2 ) = n * ( (n^2) + n/2 )

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

Which would be (n^3) + (n^2)/2 = O(n^3) ?

我肯定我这样做是错误的。为什么不是为O（n ^ 3）？

I am positive I am doing this wrong. Why isn't O(n^3)?

推荐答案

您是正确的，外层循环迭代n次，内部循环迭代n次为好，但你是重复计算的工作。如果算上向上和总结整个顶层循环的每次迭代完成你得到的第一迭代确实Ñ工作，第二n的工作完成的总功 - 1，第三个N - 2等，由于第i个顶层循环迭代有内环做 N - 我工作

You are correct that the outer loop iterates n times and the inner loop iterates n times as well, but you are double-counting the work. If you count up the total work done by summing the work done across each iteration of the top-level loop you get that the first iteration does n work, the second n - 1, the third n - 2, etc., since the ith iteration of the top-level loop has the inner loop doing n - i work.

另外，你可以指望由工作由内部循环时间做的次数循环运行的总数量乘以所做的工作。内环确实为O（n）在每个迭代的工作，和外循环运行为O（n）的迭代，所以总的工作是O（n ² ）。

Alternatively, you could count up the work done by multiplying the amount of work done by the inner loop times the total number of times that loop runs. The inner loop does O(n) work on each iteration, and the outer loop runs for O(n) iterations, so the total work is O(n²).

您正试图通过这两种策略相结合犯错误。这是真的，外环并在第一时间n的工作，则n - 1，则n - 2，等，但是，不进行n乘以这项工作，以获得总。这将算在每次迭代n次。相反，你可以归纳在一起。

You're making an error by trying to combine these two strategies. It's true that the outer loop does n work the first time, then n - 1, then n - 2, etc. However, you don't multiply this work by n to to get the total. That would count each iteration n times. Instead, you can just sum them together.

希望这有助于！

这篇关于为什么会冒泡排序为O（n ^ 2）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！