我很困惑，我以为您将 Big O 用于最坏情况的运行时间，而 Ω 用于最好的情况？有人可以解释一下吗？
(lg n) 不是最好的情况吗？和 (nlg n) 是最坏的情况？还是我误解了什么？
证明 Max-Heapify 在大小为 n 的堆上的最坏情况运行时间为 Ω(lg n)。（提示：对于具有 n 个节点的堆，给出节点值，使 Max-Heapify 在从根到叶的路径上的每个节点处被递归调用。）
编辑：不，这不是家庭作业。我正在练习，这有一个答案键购买我很困惑。 http://www-scf.usc.edu/~csci303/cs303hw4solutions.pdf问题 4(6.2 - 6)
编辑2：所以我误解了不是关于大O和Ω的问题？
区分 case 和 bound 很重要。
在分析算法时，最佳、平均和最差是常见的关注案例。
上 (O, o) 和下 (Omega, omega) 以及 Theta 是函数的常见界限。
当我们说“算法 X 的最坏情况时间复杂度是 O(n)”时，我们是说当我们将输入限制为最坏情况输入时，代表算法 X 性能的函数是由某个线性函数从上面渐近限制的. 您可以说最坏情况输入的下限；或平均或最佳案例行为的上限或下限。
案例！=绑定。就是说，“最坏的上限”和“最好的下限”是非常明智的指标……它们为算法的性能提供了绝对界限。这并不意味着我们不能谈论其他指标。
编辑以回复您更新的问题：
该问题要求您证明 Omega(lg n) 是最坏情况行为的下限。换句话说，当这个算法对一类输入做尽可能多的工作时，它所做的工作量增长至少与 (lg n) 一样快，渐近。所以你的步骤如下：（1）确定算法的最坏情况；(2) 在属于最坏情况的输入上找到算法运行时间的下限。
这是寻找线性搜索的方式的说明：
在线性搜索的最坏情况下，目标项目不在列表中，必须检查列表中的所有项目以确定这一点。因此，该算法的最坏情况复杂度的下限为 O(n)。
需要注意的重要一点：对于许多算法，大多数情况下的复杂性将受到一组通用函数的上下限制。Theta 必然适用是很常见的。因此，无论如何，您可能不会得到与 O 不同的答案。
O 是上限（即最坏情况） Ω 是下限（即最好情况）
这个例子是说在 max-heapify 的最差输入中（我猜最差的输入是逆序输入），运行时间复杂度必须（至少）是 lg n 。因此 Ω (lg n) 因为它是执行复杂度的下限。
实际上，您将 Big O 用于增长速度快于最坏情况复杂度的函数，而使用 Ω 表示增长速度比最坏情况复杂度更慢的函数。
所以在这里你被要求证明你的最坏情况复杂度比 lg(n) 差。