algorithm - 大 O 代表最坏情况运行时间，Ω 代表最好情况，但为什么有时 Ω 用于最坏情况？

Question

我很困惑，我以为你使用 Big O 表示最坏情况下的运行时间，而 Ω 表示最好情况？有人可以解释一下吗？

(lg n) 不是最好的情况吗？并且 (nlg n) 是最坏的情况？还是我误会了什么？

Show that the worst-case running time of Max-Heapify on a heap of size n is Ω(lg n). ( Hint: For a heap with n nodes, give node values that cause Max-Heapify to be called recursively at every node on a path from the root down to a leaf.)

编辑:不，这不是家庭作业。我在练习，这有一个答案，我很困惑。 http://www-scf.usc.edu/~csci303/cs303hw4solutions.pdf习题4(6.2 - 6)

编辑 2:所以我误解了与 Big O 和 Ω 无关的问题？

Answer 1

区分 case 和 bound 很重要。

最佳、平均和最差是分析算法时感兴趣的常见情况。

上限 (O, o) 和下限 (Omega, omega) 以及 Theta 是函数的常见边界。

当我们说“算法 X 的最坏情况时间复杂度为 O(n)”时，我们是说表示算法 X 性能的函数，当我们将输入限制为最坏情况输入时，从上方渐近地有界为一些线性函数。您可以谈论最坏情况输入的下限；或平均或最佳案例行为的上限或下限。

案例 != 绑定(bind)。也就是说，“最差的上限”和“最好的下限”是相当明智的度量标准……它们提供了算法性能的绝对界限。这并不意味着我们不能谈论其他指标。

编辑以回复您更新的问题:

该问题要求您证明 Omega(lg n) 是最坏情况行为的下界。换句话说，当这个算法对一类输入做尽可能多的工作时，它所做的工作量至少以渐进的速度增长到 (lg n)。因此，您的步骤如下: (1) 确定算法的最坏情况； (2) 在属于最坏情况的输入上找到算法运行时间的下界。

这是寻找线性搜索的方式的说明:

在线性搜索的最坏情况下，目标项不在列表中，必须检查列表中的所有项才能确定这一点。因此，该算法最坏情况复杂度的下限为 O(n)。

需要注意的重要事项:对于许多算法，大多数情况下的复杂性将受到一组通用函数的限制。和以下。应用 Theta 绑定(bind)是很常见的。因此，在任何情况下，很可能您对 Omega 的回答与对 O 的回答不同。