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

Question

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

鉴于冒泡排序的一个主要特点是（输入大小减去迭代）之后的元素永远不需要再次比较，因为它在正确的位置，为什么冒泡排序时间复杂度说是对我来说我不认为是冒泡排序的东西？即使在维基百科中，它也说时间复杂度是 O(n^2)，然后在文章的中途它提到它可以是 "optimised" 通过不不必要地比较最后一个 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

With 400 objects a time complexity of O(n^2) would be 400 * 400 = 160,000. However it only did 79,800 comparisons, roughly 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" - 它描述了当参数趋向于特定值或无穷大时函数的限制行为。

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

Why is bubble sort time complexity referred to as n squared?

c

big-o

bubble-sort

time-complexity