我正在学习算法分析。我理解算法的最坏情况运行时间概念。
然而,什么是算法最坏情况运行时间的上界和下界呢?
可以举一个例子,其中算法最坏情况运行时间的上界不同于相同算法的最坏情况运行时间的下界吗?
我正在学习算法分析。我理解算法的最坏情况运行时间概念。
然而,什么是算法最坏情况运行时间的上界和下界呢?
可以举一个例子,其中算法最坏情况运行时间的上界不同于相同算法的最坏情况运行时间的下界吗?
最坏情况/平均情况(或任何其他情况)会影响复杂度函数,但大O、大Ω和大Theta可以应用于每种情况。
例如,哈希表插入的平均情况是Θ(1)
,最坏情况插入是Θ(n)
。它还是O(n)
平均情况插入(边界不紧),Ω(1)
最坏情况插入。
最坏情况下的下界: 一种函数,它是算法运行时间函数下面的边界,当该算法给出使算法运行时间最大化的输入时。
最坏情况上界: 一种函数,它是算法运行时间函数上面的边界,当该算法给出使算法运行时间最大化的输入时。
最佳情况下界: 一种函数,它是算法运行时间函数下面的边界,当该算法给出使算法运行时间最小化的输入时。
最佳情况上界: 一种函数,它是算法运行时间函数上面的边界,当该算法给出使算法运行时间最小化的输入时。
让我们举几个具体的例子,说明我们何时关心这些内容:
最坏情况下的下界: 经典例子是基于比较的排序,其在最坏情况下被广泛认为是Ω(n log(n))。无论你设计什么算法,我都可以选择一组最坏情况的输入,使得最紧密的下界函数是对数线性的。你不能制作一个能够在最坏情况下打败这个下界的算法,也不应该试图去尝试。这是排序的底部。当然,最坏情况下有许多下界: 常数、线性和亚线性都是下界。但它们并不是有用的下界,因为对数线性下界是最紧密的。
最好情况下的下界: 插入排序通过遍历列表,并将任何遇到的乱序插入到正确的位置中。如果列表已经排序,则只需要遍历列表一次而不进行任何插入。这意味着最好情况下的最紧密下界是Ω(n)。除非牺牲正确性,否则你不能做得更好,因为你仍然需要能够遍历列表(线性时间)。然而,最好情况下的下界比最坏情况下的下界要好!
最坏情况的上界:我们经常有兴趣找到最坏情况下的紧密上界,因为这样我们就知道算法在最坏情况下的表现有多差。插入排序的最坏情况是一个完全无序的列表(即与其正确顺序完全相反)。每次看到一个新项目时,我们都必须将其移动到列表的开头,推动所有后续项目向前移动(这是一个线性时间操作,在线性次数执行会导致二次行为)。然而,我们仍然知道这种插入行为在最坏情况下将是O(n2),作为最坏情况的紧密上界。虽然不是很好,但比指数或阶乘等上界要好!当然,那些也是最坏情况的有效上界,但再次知道二次是紧密上界更有用。
最优情况下的上界:我们的算法在最好的情况下能做到最坏的情况是什么?例如,在查找列表中的元素时,如果第一个元素就是我们需要的元素,那么最坏情况的时间复杂度为O(1)。在最坏情况下,时间复杂度是线性的,但在最优情况下,最坏的情况仍然是常数级别的。在我看来,这个特定的想法通常不像最坏情况下的上界那样重要,因为我们通常更关心如何处理最坏情况,而不是最优情况。
其中一些例子实际上是Ө,而不仅仅是O和Ω。在其他情况下,我可能会选择不太紧密的下界或上界函数,但它们仍然足够近似以便有用(请记住,如果我们没有很紧密的限制,我有一个无限的选择!)。请注意,找到不同情况/上下界组合的有力例子可能很困难,因为这些组合具有不同的实用性。
让我通过一个例子来说明:
快速排序的最差情况运行时间是Theta(n^2)
。因此,一个有效的下界将是Omega(n)
,而上界将是O(n^3)
。这意味着在最坏的情况下,快速排序将需要至少线性时间和最多立方时间。
现在这不是一个非常精确的陈述,但对于更复杂的算法,这样的陈述是我们所能做到的最好的。
f(n)
,那么我们可以像上面提到的那样找到上限和下限吗? - Amulya Kharef(n)
[如果我们能找到,那就太容易了],所以你找到一个g(n)
,它是算法的上限,并将你的算法表示为O(g(n))
。 - amit