算法的最坏情况运行时间的上限与下限比较

Question

算法的最坏情况运行时间的上限与下限比较

algorithmcomplexity-theory

16

我正在学习算法分析。我理解算法的最坏情况运行时间概念。

然而，什么是算法最坏情况运行时间的上界和下界呢？

可以举一个例子，其中算法最坏情况运行时间的上界不同于相同算法的最坏情况运行时间的下界吗？

- Amulya Khare

3个回答

6

首先，让我们来谈谈案例。一个算法的输入案例与问题的实例相关。以排序问题为例（我们想要在特定顺序下找到一组集合的排列），我可以看作是一个包含数字 {1, 5, 4, 2, 6} 的集合实例。这个数字集合将会成为排序算法的输入，比如选择排序或者其他排序算法。

相同的输入可以提供给任何想要解决问题的算法。使用哪种排序算法并不重要，因为输入集始终相同（因为它们都是相同问题的实例）。但是，对于给定的算法，某个特定情况可能更好或更差。有些算法无论输入是什么都会执行相同的操作，但是有些算法在某些输入上可能表现更差。然而，这意味着每个算法都有一些最佳情况和最坏情况；我们有时也谈论平均情况（通过取所有情况的平均值）或预期情况（当我们有理由预期某种情况比其他情况更常见时）。

算法案例

“查找未排序列表的最小值”问题对于每个可能的输入始终起作用。无论你写了多么聪明的算法，你都必须检查每个元素。无论你有一个由零组成的列表、随机数字的列表还是第一个元素是最小值的列表，你直到到达末尾才知道。对于该算法，每种情况都是相同的，因此最佳情况和最坏情况以及平均情况和预期情况都是相同的。如果列表已排序，我们可以做得更好，但那是另一个问题。

问题“在列表中查找给定元素”的情况是不同的。假设您使用的算法是通过列表进行线性遍历，那么可能会发现给定元素是列表的第一个元素，这样您就可以立即完成了。但是，它也可能是列表的最后一个元素，在这种情况下，您必须遍历整个列表才能找到它。因此，您有一个最好情况和最坏情况。

算法作为输入大小的函数

当我们想要分析算法时，我们算法师考虑我们可以对算法进行的每种可能情况。通常，最有趣的两种情况是最佳情况和最坏情况。如果您将算法运行时间视为其输入的函数，则最佳情况是使函数最小化的输入，而最坏情况是使函数最大化的输入。在这里，“函数”是指代数数学意义上的函数：一系列x / y对（输入/输出对或在这种情况下是“输入大小/执行步骤数”）形成一条直线。

由于算法的运行时间是其输入的函数，因此对于每个可能的输入大小，我们都有不同的最佳情况（和最坏情况）。因此，有时我们将最佳情况视为单个输入，但实际上它是一组输入（每个输入大小一个）。最佳情况和最坏情况是与给定算法相关的非常具体的事情。

界限（Bounds）

现在边界怎么样呢？界限是我们用来与给定算法函数进行比较的函数。我们可以考虑无限数量的边界函数。你可以在图上画多少种可能的线条？这就是有多少种边界函数。大多数算法学家通常只关注少数特定的函数：诸如常数函数、线性函数、对数函数、指数函数等等。

上界是一个坐在另一个函数顶部的函数。下界是一个坐在另一个函数底部的函数。当我们谈论大O和大Omega时，我们并不在乎界限是否总是在其他函数的上方或下方，只要在某个点之后它们总是在上面或下面即可（因为有时算法在小的输入大小时会变得很奇怪）。

任何给定函数都有无数个可能的上界和下界。但这是一种关于不同大小的无限性的奇怪情况。为了成为上界，函数必须不低于另一个函数，因此我们排除了比另一个函数更小的无限多个函数（因此它比所有可能的函数集合更小）。

当然，仅仅因为存在无限的上界，并不意味着它们都有用。函数f（∞）是每个函数的上界，但这就像说“我拥有的钱不到无穷大”——对于确定我是否一文不名或百万富翁并不特别有用。因此，我们通常对紧密的上界感兴趣（也称为“最小上界”或“上确界”），其中没有更好的上界。

我们有代表算法运行时间函数的上下函数的最好/最坏情况。我们有代表其他函数的上下界，这些函数可以在任何其他函数之上或之下（分别）。它们可以结合起来阐述关于算法的关键思想。

最坏情况下的下界: 一种函数，它是算法运行时间函数下面的边界，当该算法给出使算法运行时间最大化的输入时。

最坏情况上界: 一种函数，它是算法运行时间函数上面的边界，当该算法给出使算法运行时间最大化的输入时。

最佳情况下界: 一种函数，它是算法运行时间函数下面的边界，当该算法给出使算法运行时间最小化的输入时。

最佳情况上界: 一种函数，它是算法运行时间函数上面的边界，当该算法给出使算法运行时间最小化的输入时。

案例边界示例

让我们举几个具体的例子，说明我们何时关心这些内容：

最坏情况下的下界: 经典例子是基于比较的排序，其在最坏情况下被广泛认为是Ω(n log(n))。无论你设计什么算法，我都可以选择一组最坏情况的输入，使得最紧密的下界函数是对数线性的。你不能制作一个能够在最坏情况下打败这个下界的算法，也不应该试图去尝试。这是排序的底部。当然，最坏情况下有许多下界: 常数、线性和亚线性都是下界。但它们并不是有用的下界，因为对数线性下界是最紧密的。

最好情况下的下界: 插入排序通过遍历列表，并将任何遇到的乱序插入到正确的位置中。如果列表已经排序，则只需要遍历列表一次而不进行任何插入。这意味着最好情况下的最紧密下界是Ω(n)。除非牺牲正确性，否则你不能做得更好，因为你仍然需要能够遍历列表（线性时间）。然而，最好情况下的下界比最坏情况下的下界要好！

最坏情况的上界：我们经常有兴趣找到最坏情况下的紧密上界，因为这样我们就知道算法在最坏情况下的表现有多差。插入排序的最坏情况是一个完全无序的列表（即与其正确顺序完全相反）。每次看到一个新项目时，我们都必须将其移动到列表的开头，推动所有后续项目向前移动（这是一个线性时间操作，在线性次数执行会导致二次行为）。然而，我们仍然知道这种插入行为在最坏情况下将是O(n2)，作为最坏情况的紧密上界。虽然不是很好，但比指数或阶乘等上界要好！当然，那些也是最坏情况的有效上界，但再次知道二次是紧密上界更有用。

最优情况下的上界：我们的算法在最好的情况下能做到最坏的情况是什么？例如，在查找列表中的元素时，如果第一个元素就是我们需要的元素，那么最坏情况的时间复杂度为O(1)。在最坏情况下，时间复杂度是线性的，但在最优情况下，最坏的情况仍然是常数级别的。在我看来，这个特定的想法通常不像最坏情况下的上界那样重要，因为我们通常更关心如何处理最坏情况，而不是最优情况。

其中一些例子实际上是Ө，而不仅仅是O和Ω。在其他情况下，我可能会选择不太紧密的下界或上界函数，但它们仍然足够近似以便有用（请记住，如果我们没有很紧密的限制，我有一个无限的选择！）。请注意，找到不同情况/上下界组合的有力例子可能很困难，因为这些组合具有不同的实用性。

误解和术语

经常会看到有误解的人关于这些定义。实际上，许多非常好的计算机科学家会随意地和互换使用这些术语。然而，案例和边界的概念是不同的，你最好确保你理解它们。这是否意味着差异会在你的日常生活中出现？不。但当你在几种不同的算法之间进行选择时，你需要阅读有关案例和边界的细则。有人告诉你他们的算法具有O(1)的最佳情况上限，可能正在欺骗你——确保你问他们最坏情况上限是什么！

- Austin Cory Bart

2

让我通过一个例子来说明:

快速排序的最差情况运行时间是Theta(n^2)。因此，一个有效的下界将是Omega(n)，而上界将是O(n^3)。这意味着在最坏的情况下，快速排序将需要至少线性时间和最多立方时间。

现在这不是一个非常精确的陈述，但对于更复杂的算法，这样的陈述是我们所能做到的最好的。

- tskuzzy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

对于函数 f(n)，如果对于“足够大的 n”，有 f(n) <= c*g(n)（其中 c 是常数），则 g(n) 是它的一个上界（big O）[g 占优势]。如果对于“足够大的 n”，有 f(n) >= c*g(n)（其中 c 是常数），则 g(n) 是它的一个下界（big Omega）[f 占优势]。

如果 g(n) 同时是 f(n) 的上界和下界 [使用不同的 c]，我们称 g(n) 是 f(n) 的紧密界限 [Big theta]。

使用上界示例而不是紧密界限：有时很难找到紧密界限，例如 fibonacci 递归算法。因此，我们可以轻松地找到 O(2^n) 的简单上界。更多信息可以在这个 post 中的答案中找到。

与最坏/基本/... 情况有什么关系？（根据评论要求）

最坏情况/平均情况（或任何其他情况）会影响复杂度函数，但大O、大Ω和大Theta可以应用于每种情况。

例如，哈希表插入的平均情况是Θ(1)，最坏情况插入是Θ(n)。它还是O(n)平均情况插入（边界不紧），Ω(1)最坏情况插入。