冒泡排序最佳时间复杂度o(n)如何？

Question

考虑到无论如何都会遍历循环，这不是 o(n²) 吗？还有一个标准化的冒泡排序算法，考虑到当被问及最好和最坏的情况时，显然有很多变体需要考虑？我是新的抱歉，如果这是一个不好的问题。

Answer 1

有人可以实现一个糟糕的冒泡排序版本，无论是否发生任何交换，都会使

n

通过，而且即使在最好的情况下，这样的实现也确实是

O(n^2)

，是的。

但是你问冒泡排序的最佳情况时间复杂度是多少

O(n)

，所以答案是它适用于冒泡排序的good实现。如果某些遍不交换任何内容，则冒泡排序的典型实际实现将终止。因此，如果输入已经排序，它只会进行一次传递，这意味着算法的最佳情况行为是

O(n)

。