为什么冒泡排序O(n ^ 2)？

Question

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次.

外循环迭代: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)？

Answer 1

你是正确的,外循环迭代n次,内循环迭代n次,但你重复计算工作.如果通过对顶层循环的每次迭代中完成的工作求和来计算总工作量,那么第一次迭代就可以工作,第二次是n - 1,第三次是n - 2,等等,因为第i次迭代顶级循环的迭代使内循环n - i起作用.

或者,您可以通过将内循环完成的工作量乘以循环运行的总次数来计算完成的工作.内部循环在每次迭代时都执行O(n)工作,外部循环运行O(n)次迭代,因此总工作量为O(n ²).

您试图将这两种策略结合起来,从而产生错误.确实,外循环第一次运行,然后是n - 1,然后是n - 2,等等.但是,你不要将这个工作乘以n来得到总数.这将计算每次迭代n次.相反,你可以把它们加在一起.

希望这可以帮助!

Answer 2

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