算法的上界和下界

Question

我看到几篇文章将上限描述为最佳案例,将下限描述为最坏情况.同时,一些文章对最坏情况的上下限进行了解释.

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

1. 什么是上/下界？
2. 如何在最坏情况场景中单独定义它们？
3. 是否可以为其他案例(最佳,平均)定义界限？

Answer 1

几乎没有人讨论最好的情况。根本没那么有趣。只要识别一个特定的输入并为该输入预先计算输出，就可以将算法修改为理论上最小的最佳情况，即O（max（输入大小，输出大小））。在基准测试业务中，这被称为作弊。

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

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

由于可以创建任意错误的排序算法，因此排序算法集的复杂度没有上限。

另一方面，我们可以讨论一种特定的排序算法，并证明它不会超过一定数量的操作，这将是其复杂性的上限。例如，快速排序算法的上限为O（n ²）。它还具有O（n ³）的上限。它不是有上限的O（N log n）的，因为有投入，使之超过此数量的操作。O（n ²）的边界很严格，因为某些输入可以达到该边界。

从理论上讲，可以按照与上述相同的方式讨论下限，但是几乎从来没有做到过（这等于讨论最好情况下的复杂性，我们通常对此并不感兴趣）。

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

Answer 2

\n

上限/下限到底是什么？

\n

\n\n

我们对函数的界限感兴趣，您可以在维基百科中阅读到。

\n\n

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

\n\n

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

\n\n

\n

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

\n

\n\n

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

\n\n

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

\n\n

\n

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

\n

\n\n

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

\n