算法 – 最坏情况运行时间的大O和Ω是最好的情况,但为什么有时在

发布时间：2020-12-15 00:24:35 所属栏目：Java 来源：网络整理

导读：我很困惑,我认为你在最坏的情况下使用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). (

我很困惑,我认为你在最坏的情况下使用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和Ω的问题？

解决方法

区分案例和界限很重要.

最佳,平均和最差是分析算法时常见的常见情况.

上部(O,o)和下部(Omega,omega)以及Theta是函数的共同边界.

当我们说“算法X的最坏情况时间复杂度是O(n)”时,我们说当我们将输入限制为最坏情况输入时,表示算法X性能的函数是通过某种线性函数从上面渐近限定的. .你可以说最坏情况输入的下限;或平均或最佳案例行为的上限或下限.

案例！=绑定.也就是说,“最糟糕的上层”和“最好的上层”是相当明智的衡量标准……它们提供了算法性能的绝对界限.这并不意味着我们不能谈论其他指标.

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

这个问题要求你证明Omega(lg n)是最坏情况行为的下限.换句话说,当这个算法对一类输入所做的工作尽可能多时,它所做的工作量至少与(lg n)一样快,渐近地增长.所以你的步骤如下：(1)确定算法的最坏情况; (2)在属于最坏情况的输入上找到算法运行时的下限.

以下是线性搜索的示意图：

在线性搜索的最坏情况下,目标项不在列表中,并且必须检查列表中的所有项以确定这一点.因此,该算法的最坏情况复杂度的下限是O(n).

需要注意的重要事项：对于大量算法而言,大多数情况下的复杂性将通过一组通用函数从上方和下方进行限制. Theta必然会适用.因此,无论如何,你很可能不会得到Omega的答案,而不是O.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!