time-complexity - 快速选择最坏情况（Θ(n^2) 还是 O(n^2)？）

Question

我一直在尝试理解快速选择算法，并且我发现了最坏情况运行时间复杂度的两个不同值。

例如，该网站声称最坏情况的时间复杂度是 Θ(n^2)，而GeeksforGeeks声称它是 O(n^2)。

有人可以帮我理解哪一个是正确的，为什么会这样？

Answer 1

两者都是正确的，但使用 Θ 是一个更强的陈述。大 O 表示法给出了渐近的上限，而大的 Theta 表示法给出了实际的渐近增长率。

作为一个类比，想象 Alice 和 Bob 都在数某人的腿。爱丽丝说legs = 2，鲍勃说legs ≤ 2。爱丽丝和鲍勃都是正确的，但爱丽丝的陈述更有力。

在非正式使用中，当你可以用 Θ 写出更强的语句时，写 O 是很常见的，因为大多数人的键盘没有 Θ 键。