什么是大哦或大欧米茄"complexity of operation in the worst case"

Question

我对术语用法感到困惑。如果人们说"最坏情况下操作的复杂性"，他们的意思是什么：下限还是上限？

Answer 1

大多数人的意思是紧界（即既是上界又是下界的界），通常用大θ（大θ）表示法给出。许多只对形式主义略知一二的人使用大O表示法，这意味着上界，但实际上意味着下界。

有些人把自己限制在一个上限，因为他们不确定自己的界限是否严密。

事实上，没有人在讨论下限时不明确地这么说

然而，请注意，情况的类型（最佳/平均/最差/…）和边界的类型（上/下/紧）是正交的：在情况X中，复杂度恰好为θ；给出最坏情况复杂度的下界或最佳情况复杂度上限是完全合理的。