6

我看到几篇文章将上限描述为最佳情况，将下限描述为最坏情况。同时也有文章对Worst Case的上/下界给出了解释。

所以基本上这让我问了三个问题：

  1. 究竟什么是上限/下限？
  2. 在最坏情况下如何单独定义它们？
  3. 是否也可以为其他情况（最佳、平均）定义界限？
4

2 回答 2

6

几乎从不讨论最好的情况。它根本没那么有趣。算法总是可以修改为具有最小的理论上可能的最佳情况，即 O(max(size-of-input, size-of-output))，只需识别一个特定的输入并生成为该输入预先计算的输出。在基准测试业务中，这被称为作弊。

这里的术语“界”与其他数学中的含义相同，即不大于（不小于）给定集合的任何元素的任意值。

例如，在讨论排序算法集时，我们可以证明在最坏情况下（以及在平均情况下），没有任何基于比较的排序算法比 O(n log n) 具有更好的渐近效率。因此 O(n log n) 是所有可能的基于比较的排序算法在最坏情况下（以及平均情况下）效率的下限。O(n) 是另一个下限。O(n log n) 是比 O(n) 更好的下限。恰好 O(n log n) 是紧 的下限，因为实际上存在具有这种复杂性的排序算法。

排序算法集的复杂性没有有限的上限，因为可以创建任意错误的排序算法。

另一方面，我们可以讨论一个特定的排序算法，并证明它永远不会超过一定数量的操作，这将是其复杂性的上限。例如，快速排序算法的上限为 O(n 2 )。它还具有 O(n 3 )的上限。它没有O (n log n) 的上限，因为有输入使它超过了这个操作数。O(n 2 )的界限很紧，因为它是针对某些输入实现的。

理论上可以以与上述相同的意义讨论下限，但这几乎从未做过（这相当于讨论最佳情况的复杂性，我们通常对此并不感兴趣）。

我们还可以讨论特定问题的难度，并为其设置上限和下限。解决它的最有效算法（在最坏或平均情况下）的效率如何？（我们不讨论最好的情况，因为答案并不有趣，见上文）。对于基于比较的排序问题，我们知道紧上界和紧下界都是 O(n log n)，因为实际上有 O(n log n) 的排序算法，可以证明没有更好的算法存在。这不是一个非常有趣的案例，因为我们可以找到最有效的算法。例如，背包问题的情况更有趣。我们只知道 O(2 n) 存在是因为具有这种复杂性的算法微不足道地存在（蛮力算法）。我们怀疑但不能证明这个界限很紧。我们也不能提供任何好的下界（我们怀疑没有算法可以用多项式复杂度解决它，但无法证明它）。

于 2017-05-25T12:17:58.980 回答
0

究竟什么是上限/下限？

我们对函数的边界感兴趣，您可以在Wikipedia中阅读。

此外，这个答案的一部分提到：

对于一个函数f(n)，如果对于“足够大的 n” ，g(n)是一个上限（大 Of(n)<=c*g(n) ） ，对于一个常数c。[g 支配 f]
g(n) 是下界（大欧米茄）如果对于“足够大的 n” f(n) >= c*g(n)，对于一个常数c。[f 支配 g]

在最坏情况下如何单独定义它们？

它们要么不同，要么相同；在这种情况下，我们说 Θ(n)，其中 n 通常是问题的大小。正如杜克林所说：

更糟糕的是，最好的和平均的情况可以*表示为一个函数（用于终止算法）。这些函数中的每一个都有上限和下限（其中有无限多个）。对每个元素执行恒定数量的操作（例如，插入排序的最佳情况和线性搜索的平均/最差情况）将具有 Θ(n) 的紧密界限（下限和上限），但也有 O( n 2 ) 或Ω(1) 的下限。

是否也可以为其他情况（最佳、平均）定义界限？

是的。可能所有情况都有其上限和下限。

于 2017-05-25T11:17:05.940 回答