算法中的上限和下限
Upper bounds and Lower bounds in Algorithms
我看到几篇文章将上限描述为最佳情况，将下限描述为最坏情况。同时也有文章对Upper/Lower bound of Worst Case进行了解释。
基本上这让我问了三个问题：
- Upper/Lower 边界到底是什么？
- 如何在最坏情况下分别定义它们？
- 是否也可以为其他情况（最佳、平均）定义界限？
What exactly are Upper/Lower bounds?
我们对函数的边界感兴趣，您可以在 Wikipedia 中阅读。
此外，answer的一部分提到：
对于函数 f(n)，g(n) 是 上限 (big O) 如果对于 "big enough n"，f(n)<=c*g(n)，为常量 c。 [g 支配 f]
g(n) 是 下限 (big Omega) 如果对于 "big enough n", f(n) >= c*g(n), 对于常数 c. [f支配g]
How can they be defined separately in a Worst Case scenario?
它们要么不同，要么相同；在那种情况下，我们说 Θ(n)，其中 n 通常是问题的大小。正如杜克林所说：
最差、最佳和平均情况可以*表示为一个函数（用于终止算法）。这些函数中的每一个都有上限和下限（其中有无限多个）。对每个元素执行恒定数量的操作（例如，插入排序的最佳情况和线性搜索的 average/worst 情况）将具有 Θ(n) 的紧界（下界和上界），但也有上界O(n2) 或 Ω(1).
的下界
Can bounds be defined for other cases(Best,Average) as well?
是的。可能所有情况都有上下界。
人们几乎从不讨论最好的情况。这根本就没那么有趣。算法总是可以修改为具有最小的理论上可能的最佳情况，即 O(max(输入大小，输出大小))，只需识别一个特定输入并生成针对该输入预先计算的输出。在基准测试业务中，这被称为作弊。
这里的术语绑定与其他数学中的含义相同，即不大于（不小于）给定集合的任何元素的任意值。
比如在讨论排序算法集的时候，我们可以证明，在最坏的情况下，没有比O(n log n)更好的渐近效率的基于比较的排序算法（在一般情况下也是如此）。因此，O(n log n) 是所有可能的基于比较的排序算法在最坏情况下（以及平均情况下）效率的 a 下限。 O(n) 是另一个下界。 O(n log n) 是比 O(n) 更好的下界。恰好 O(n log n) 是 the tight lower bound，因为实际上有这种复杂度的排序算法。
排序算法集的复杂度没有上限，因为可以创建任意糟糕的排序算法。
另一方面，我们可以讨论一个特定的排序算法，并证明它永远不会超过一定数量的操作，这将是其复杂性的上限。例如，快速排序算法的上限为 O(n2)。它还具有 O(n3) 的上限。它确实 not 具有 O(n log n) 的上限，因为有输入使其超过此操作数。 O(n2) 的界限很紧，因为它是针对某些输入达到的。
理论上可以像上面一样讨论下界，但几乎从未有人这样做过（这相当于讨论最好情况的复杂性，我们通常对此不感兴趣）。
我们还可以讨论特定问题的难度，并为其设置上限和下限。解决它的最有效算法（在最坏或平均情况下）的效率如何？ （我们不讨论最好的情况，因为答案并不有趣，见上文）。对于基于比较的排序问题，我们知道紧上界和紧下界都是 O(n log n) 因为实际上有 O(n log n) 排序算法并且可以证明没有更好的算法存在。这不是一个非常有趣的案例，因为我们可以找到最有效的算法。例如背包问题的情况更有趣。我们只知道 O(2n) 的上限存在，因为具有这种复杂性的算法平凡存在（蛮力算法）。我们怀疑但不能证明这个界限很紧。我们也无法提供任何好的下界（我们怀疑没有算法可以用多项式复杂度解决它但无法证明它）。
我看到几篇文章将上限描述为最佳情况，将下限描述为最坏情况。同时也有文章对Upper/Lower bound of Worst Case进行了解释。
基本上这让我问了三个问题：
- Upper/Lower 边界到底是什么？
- 如何在最坏情况下分别定义它们？
- 是否也可以为其他情况（最佳、平均）定义界限？
What exactly are Upper/Lower bounds?
我们对函数的边界感兴趣，您可以在 Wikipedia 中阅读。
此外，answer的一部分提到：
对于函数 f(n)，g(n) 是 上限 (big O) 如果对于 "big enough n"，f(n)<=c*g(n)，为常量 c。 [g 支配 f]
g(n) 是 下限 (big Omega) 如果对于 "big enough n", f(n) >= c*g(n), 对于常数 c. [f支配g]
How can they be defined separately in a Worst Case scenario?
它们要么不同，要么相同；在那种情况下，我们说 Θ(n)，其中 n 通常是问题的大小。正如杜克林所说：
最差、最佳和平均情况可以*表示为一个函数（用于终止算法）。这些函数中的每一个都有上限和下限（其中有无限多个）。对每个元素执行恒定数量的操作（例如，插入排序的最佳情况和线性搜索的 average/worst 情况）将具有 Θ(n) 的紧界（下界和上界），但也有上界O(n2) 或 Ω(1).
的下界Can bounds be defined for other cases(Best,Average) as well?
是的。可能所有情况都有上下界。
人们几乎从不讨论最好的情况。这根本就没那么有趣。算法总是可以修改为具有最小的理论上可能的最佳情况，即 O(max(输入大小，输出大小))，只需识别一个特定输入并生成针对该输入预先计算的输出。在基准测试业务中，这被称为作弊。
这里的术语绑定与其他数学中的含义相同，即不大于（不小于）给定集合的任何元素的任意值。
比如在讨论排序算法集的时候，我们可以证明，在最坏的情况下，没有比O(n log n)更好的渐近效率的基于比较的排序算法（在一般情况下也是如此）。因此，O(n log n) 是所有可能的基于比较的排序算法在最坏情况下（以及平均情况下）效率的 a 下限。 O(n) 是另一个下界。 O(n log n) 是比 O(n) 更好的下界。恰好 O(n log n) 是 the tight lower bound，因为实际上有这种复杂度的排序算法。
排序算法集的复杂度没有上限，因为可以创建任意糟糕的排序算法。
另一方面，我们可以讨论一个特定的排序算法，并证明它永远不会超过一定数量的操作，这将是其复杂性的上限。例如，快速排序算法的上限为 O(n2)。它还具有 O(n3) 的上限。它确实 not 具有 O(n log n) 的上限，因为有输入使其超过此操作数。 O(n2) 的界限很紧，因为它是针对某些输入达到的。
理论上可以像上面一样讨论下界，但几乎从未有人这样做过（这相当于讨论最好情况的复杂性，我们通常对此不感兴趣）。
我们还可以讨论特定问题的难度，并为其设置上限和下限。解决它的最有效算法（在最坏或平均情况下）的效率如何？ （我们不讨论最好的情况，因为答案并不有趣，见上文）。对于基于比较的排序问题，我们知道紧上界和紧下界都是 O(n log n) 因为实际上有 O(n log n) 排序算法并且可以证明没有更好的算法存在。这不是一个非常有趣的案例，因为我们可以找到最有效的算法。例如背包问题的情况更有趣。我们只知道 O(2n) 的上限存在，因为具有这种复杂性的算法平凡存在（蛮力算法）。我们怀疑但不能证明这个界限很紧。我们也无法提供任何好的下界（我们怀疑没有算法可以用多项式复杂度解决它但无法证明它）。