最坏情况下的运行时间复杂度用Big O表示，最好情况下用Ω表示，但为什么有时候最坏情况下也会使用Ω？

Question

10

我有些困惑，我以为在描述最坏情况的运行时间时要使用大O符号，而Ω符号用于最好情况？能否有人解释一下？

那么(lg n)不是最好情况吗？(nlg n)才是最差情况？或者我误解了什么？

证明堆大小为n时Max-Heapify的最坏情况运行时间是Ω(lg n)。（提示：对于具有n个节点的堆，给出节点值，使得从根到叶子的每个节点上都会递归调用Max-Heapify。）

编辑：不，这不是作业。我正在练习，这有一个答案，但我感到困惑。 http://www-scf.usc.edu/~csci303/cs303hw4solutions.pdf问题4（6.2-6）

编辑2：所以我误解了问题，它与大O和Ω无关？

- jantristanmilan

1

@Gumbo在你的链接中提到了他的分析是最坏情况：Theta(logn + k)，难道不应该是Theta(logn)吗？因为你可以忽略+k。 - jantristanmilan

1

是的，找到其他k-1个附近的标题将是微不足道的。 - Gumbo

Ω(1)是最好的情况;-) - hertzsprung

3个回答

-1

实际上，你使用大O符号表示增长速度比最坏情况复杂度还要快的函数，使用Ω符号表示增长速度比最坏情况复杂度更慢的函数。

所以在这里，你需要证明你的最坏情况复杂度比lg(n)还要糟糕。

- Axelle Ziegler

"比 lg(n) 更差" - 或许你应该说 "渐进地更大于（asymptotic greater than）"。 - Zeta

所以我误解了问题，不是关于大O和Ω吗？ - jantristanmilan

在我们的考试中，你必须说“更糟”，因为如果它更大，那就更糟了，对吧？ - jantristanmilan

-1

O是上限（即最坏情况） Ω是下限（即最好情况）

这个例子是说在max-heapify的最坏输入情况下（我猜最坏输入是反向排序的输入），运行时间复杂度必须是（至少）lg n。因此，Ω（lg n）是执行复杂度的下限。

- fabiim

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Patrick87 · Accepted Answer

重要的是要区分案例和边界。

在分析算法时，最好、平均和最差是常见的感兴趣的案例。

上限（O，o）和下限（Omega，omega）以及Theta是函数的常见边界。

当我们说“算法X的最坏时间复杂度是O（n）”时，我们是说代表算法X性能的函数，在将输入限制为最坏情况输入时，从上面渐近地受到某些线性函数的限制。你可以谈论最坏情况输入的下限；或者关于平均、最佳情况下行为的上限或下限。

案例!=边界。话虽如此，“最坏情况下的上限”和“最好情况下的下限”是相当合理的指标……它们提供了算法性能的绝对边界。这并不意味着我们不能谈论其他指标。

编辑以回答您更新后的问题：

该问题要求您展示Omega（lg n）是最坏情况下行为的下界。换句话说，当该算法尽可能多地完成一类输入的工作时，它所做的工作量至少与（lg n）一样快地增长，渐近地。因此，您的步骤如下：（1）确定算法的最坏情况；（2）找到算法在属于最坏情况的输入上运行时间的下限。

这里是线性搜索的演示：

在线性搜索的最坏情况下，目标项目不在列表中，并且必须检查列表中的所有项目才能确定此项。因此，该算法最坏情况下的复杂度的下界是O（n）。

需要注意的重要一点是，对于许多算法，大多数情况的复杂度都会被常见的一组函数从上面和下面限制。 Theta边界非常常见。因此，在任何情况下，Omega和O或许没有不同的答案。