为什么冒泡排序的时间复杂度被称为n平方？

Question

关于冒泡排序时间复杂度还有其他问题，但这个问题不同。大家都说冒泡排序最坏情况是 O(n^2)。在列表 i 次迭代之后的冒泡排序中，列表的最后 i 个元素是有序的，不需要再次触摸或比较。如果你不必要地一次又一次地运行最终元素，时间复杂度只会是 O(n^2)。

鉴于冒泡排序的一个主要特征是（输入大小减去迭代）之后的元素永远不需要再次比较，因为它位于正确的位置，为什么冒泡排序的时间复杂度对我来说是这样的没想到是冒泡排序？即使在维基百科中，它也说时间复杂度是 O(n^2)，然后在文章的中间才提到，通过不不必要地比较最后 i 个元素，可以“优化”到只花费大约 50% 的时间。

我想起了这一点，因为我正在制作一个循环来检查世界上所有对象的碰撞，并且我检查的模式是：

for (int i = 0; i < numberofobjects - 1; i++)
{
   {
      for (int iplusone = i + 1; iplusone < numberofobjects; iplusone++)
        // check collision between i and iplusone
   }
}

对于 400 个对象，时间复杂度为 O(n^2) 400 * 400 = 160,000。然而它只进行了 79,800 次比较，大约是 50%，这正是维基百科所说的。这让我想起了冒泡排序，所以当我检查时，我惊讶地发现每个人都说它是 O(n^2)。

这是否意味着每当有人提到冒泡排序时，他们指的是不必要地重复已排序的最终元素的版本？此外，当比较不同的算法时，冒泡排序总是表现更差，但作者是否指的是明显糟糕的 n^2 版本？

Answer 1

对于 400 个对象，时间复杂度为 O(n^2) 400 * 400 = 160,000。然而它只进行了 79,800 次比较，大约为 50%

是的，你对 79,800 次比较的看法是正确的，但你没有很好地理解大 O 表示法。

首先，如果您仔细查看冒泡排序算法，您会注意到确切的步骤比较是：

n-1 + n-2 + ... + 1 = n(n-1)/2 exactly

这意味着，当 n=400 时，您将获得400*399/2=79,800 次比较。

尽管大 O 表示法告诉您总步骤为：n(n-1)/2 = n^2/2 - n/2在大 O 表示法中，我们忽略低阶项和常数，并且仅保留 n^2原样O(n^2)。

这里您需要理解的是，大 O 表示法不会告诉您确切的步骤，它只会告诉您一个上限，例如复杂性函数的高阶，这适用于 n 上的大值。它只是指出"for big n the complexity-order of growth is c*n^2"- 它描述了当参数趋于特定值或无穷大时函数的极限行为。