并不是(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和Ω的问题？
解决方法
最佳,平均和最差是分析算法时常见的常见情况.
上部(O,o)和下部(Omega,omega)以及Theta是函数的共同边界.
当我们说“算法X的最坏情况时间复杂度是O(n)”时,我们说当我们将输入限制为最坏情况输入时,表示算法X性能的函数是通过某种线性函数从上面渐近限定的. .你可以说最坏情况输入的下限;或平均或最佳案例行为的上限或下限.
案例！=绑定.也就是说,“最糟糕的上层”和“最好的上层”是相当明智的衡量标准……它们提供了算法性能的绝对界限.这并不意味着我们不能谈论其他指标.
编辑以回复您更新的问题：
这个问题要求你证明Omega(lg n)是最坏情况行为的下限.换句话说,当这个算法对一类输入所做的工作尽可能多时,它所做的工作量至少与(lg n)一样快,渐近地增长.所以你的步骤如下：(1)确定算法的最坏情况; (2)在属于最坏情况的输入上找到算法运行时的下限.
以下是线性搜索的示意图：
在线性搜索的最坏情况下,目标项不在列表中,并且必须检查列表中的所有项以确定这一点.因此,该算法的最坏情况复杂度的下限是O(n).
需要注意的重要事项：对于大量算法而言,大多数情况下的复杂性将通过一组通用函数从上方和下方进行限制. Theta必然会适用.因此,无论如何,你很可能不会得到Omega的答案,而不是O.
