algorithm - 为什么冒泡排序是 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)？

Answer 1

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

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

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

希望这对您有所帮助!