algorithm - 证明算法的上限和下限

Question

如何证明算法的上限和下限？

直到现在，我认为算法的上限和下限都需要通过考虑所有输入并表明它不能比 f(n) [upper bound] 并且不优于 g(n) [下限]。

我的讲师说，对于上限，需要一般性地证明它 [考虑到所有输入]，但对于下限，一个例子就足够了。

这让我很困惑。谁能解释一下他的意思？

Answer 1

如果您的讲师谈到最坏情况下的行为，他是对的。

从一个例子来看，您可以说运行时间“至少那么多”(而且可能更糟)，但不能说它“最多那么多”(因为它可能更糟)。

[对称地，当谈到最佳情况行为时，单个情况可以保证上限。]

下限和上限是完全不同的东西。下限通常是“普遍”建立的，即不考虑任何特定算法。例如，在最坏的情况下，您不能对少于 N.Log(N) 次比较的序列进行排序，因为您需要区分 N!可能的排列，这需要收集 Lg(N!) 位信息。

相反，上限是针对特定算法确定的。例如，HeapSort 永远不会超过 2N.Lg(N) 次比较。当上界满足下界时，该算法被认为是有效的。