Quick-Select 最坏情况（Θ(n^2) 或 O(n^2)？）
Quick-Select worst-case scenario (Θ(n^2) or O(n^2)?)
我一直在努力理解 Quick-Select 算法，我发现了两个不同的最坏情况 运行 时间复杂度值。
例如，This website claims that worst-case time complexity is Θ(n^2), whilst GeeksforGeeks 声称它是 O(n^2)。
谁能帮我理解哪一个是正确的，为什么会这样？
两者都是正确的，但使用 Θ 的说法更为有力。大 O 符号给出渐近上限，而大 Theta 符号给出实际渐近增长率。
打个比方，假设爱丽丝和鲍勃都在数某人的腿。爱丽丝说 legs = 2，鲍勃说 legs ≤ 2。 Alice 和 Bob 都对，但 Alice 的说法更强。
在非正式使用中，当你可以用 Θ 写出更强的语句时，写 O 是很常见的，只是因为大多数人的键盘没有 Θ 键。
我一直在努力理解 Quick-Select 算法，我发现了两个不同的最坏情况 运行 时间复杂度值。
例如，This website claims that worst-case time complexity is Θ(n^2), whilst GeeksforGeeks 声称它是 O(n^2)。
谁能帮我理解哪一个是正确的，为什么会这样？
两者都是正确的，但使用 Θ 的说法更为有力。大 O 符号给出渐近上限，而大 Theta 符号给出实际渐近增长率。
打个比方，假设爱丽丝和鲍勃都在数某人的腿。爱丽丝说 legs = 2，鲍勃说 legs ≤ 2。 Alice 和 Bob 都对，但 Alice 的说法更强。
在非正式使用中，当你可以用 Θ 写出更强的语句时，写 O 是很常见的，只是因为大多数人的键盘没有 Θ 键。