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