如何证明算法的上限和下限？
到目前为止，我认为算法的上限和下限都需要通过考虑所有输入来显示，并表明它不能比 f(n) [上限] 做得更差，也不能比 g(n) 好[下限]。
我的讲师说，对于上限，通常需要证明它[考虑到所有输入]，但对于下限，一个例子就足够了。
这真的让我很困惑。谁能澄清他的意思？
问问题
1316 次
1 回答
5
如果他谈到最坏情况的行为，你的讲师是对的。
从一个示例中，您可以说运行时间“至少那么多”（并且可能更糟），但不能说它“最多那么多”（因为它可能更糟）。
[对称地，当谈到最佳情况行为时，单个情况可以保证上限。]
下限和上限是完全不同的东西。下限通常是“普遍”建立的，即与任何特定算法无关。例如，在最坏的情况下，您不能在少于 N.Log(N) 的比较中对序列进行排序，因为您需要区分 N！可能的排列，这需要收集 Lg(N!) 位信息。
相反，上限是针对特定算法确定的。例如，HeapSort 从不超过 2N.Lg(N) 次比较。当上限满足下限时，称该算法是有效的。
于 2015-04-20T07:49:36.780 回答