问大O代表最坏的运行时间，Ω是最好的情况，但是为什么有时在最坏的情况下使用Ω？

EN

区分案件和约束是很重要的。

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

上(O，o)和下(Omega，omega)以及Theta是函数的公共界。

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

箱子！也就是说，“最坏的上”和“最好的下”是相当明智的衡量标准.它们为算法的性能提供了绝对的界限。这并不意味着我们不能谈论其他度量标准。

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

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

这里有一个例子说明了线性搜索的方式：

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

需要注意的是:对于很多算法来说，在大多数情况下，复杂度都会被一组共同的函数所限制。这是非常普遍的西塔必须申请。因此，在任何情况下，Omega的答案都不会与O的答案不同。

实际上，对于比最坏情况复杂度增长更快的函数，使用Big，对于比最坏情况复杂度增长更慢的函数，则使用Ω。

在这里，你被要求证明你最坏的情况复杂度比lg(n)更糟糕。

O是上限(即最坏的情况)，Ω是下限(即最佳情况)。

这个例子是说，对于max-heapify的最坏输入(我猜最坏的输入是反向顺序输入)，运行时间复杂度必须是(至少) lg n。因此，Ω(lg n)是执行复杂度的下限。