我看到几篇文章将上限描述为最佳情况，将下限描述为最坏情况。同时，一些文章对最坏情况的上限/下限进行了解释。
所以基本上这让我问了三个问题：
- 上限/下限到底是什么？
- 在最坏情况下如何单独定义它们？
- 也可以为其他情况(最佳，平均)定义边界吗？
人们几乎从不讨论最好的情况。这根本就没那么有趣。始终可以修改算法以具有理论上可能的最佳最小情况，即 O(max(最大输入大小，输出大小))，只需识别一个特定输入并生成为该输入预先计算的输出。在基准测试业务中，这被称为作弊。
这里的术语界限与数学的其余部分具有相同的含义，即不大于(不小于)给定集合的任何元素的任意值。
例如，在讨论排序算法集时，我们可以证明，在最坏情况下(以及在平均情况下)，没有一种基于比较的排序算法比 O(n log n) 具有更好的渐近效率。因此，O(n log n) 是所有可能的基于比较的排序算法在最坏情况下(以及在平均情况下)的效率下限。O(n) 是另一个下限。O(n log n) 是比 O(n) 更好的下限。碰巧 O(n log n) 是紧下限，因为实际上存在具有这种复杂性的排序算法。
排序算法集的复杂性没有有限的上限，因为可以创建任意错误的排序算法。
另一方面，我们可以讨论特定的排序算法，并证明它永远不会超过一定数量的操作，这将是其复杂性的上限。例如，快速排序算法的上限为 O(n2)。它的上限也是 O(n3)。它没有O(n log n) 的上限，因为有些输入使其超过此操作数。 O(n2) 的界限很紧，因为它是针对某些输入实现的。
从理论上讲，人们可以用与上述相同的意义来讨论下限，但这几乎从未被完成(这相当于讨论我们通常不感兴趣的最佳情况的复杂性)。
我们还可以讨论特定问题的难度，并对其设置上限和下限。解决该问题的最有效算法(在最坏或平均情况下)的效率如何？(我们不讨论最好的情况，因为答案并不有趣，见上文)。对于基于比较的排序问题，我们知道紧上限和紧下限都是 O(n log n)，因为实际上存在 O(n log n) 排序算法，可以证明不存在更好的算法。这不是一个非常有趣的案例，因为我们可以找到最有效的算法。例如背包问题，情况更有趣。我们只知道 O(2n) 的上限存在，因为具有这种复杂性的算法(蛮力算法)微不足道地存在。我们怀疑但不能证明这种界限是严格的。我们也不能提供任何好的下限(我们怀疑没有算法可以用多项式复杂性解决它，但不能证明它)。
上限/下限到底是什么？
我们对函数的边界感兴趣，你可以在维基百科上读到。
此外，这个答案的一部分提到：
对于函数f(n)，如果对于"足够大的n"，f(n)<=c*g(n)，对于常数c，g(n)是一个上限(大O)。[g 主导 f]
g(n) 是下限(大欧米茄)，如果对于"足够大的 n"，f(n) >= c*g(n)，对于一个常数c。[f 主导 g]
在最坏情况下如何单独定义它们？
它们要么不同，要么相同;在这种情况下，我们说Θ(n)，其中n通常是问题的大小。正如杜克林所说：
更糟糕的是，最佳和平均情况*可以表示为一个函数(用于终止算法)。这些函数中的每一个都有上限和下限(其中有无限多个)。对每个元素执行恒定数量的操作(例如，插入排序的最佳情况和线性搜索的平均/最差情况)将具有 Θ(n) 的紧边界(下限和上限)，但上限为 O(n2) 或下限为 Ω(1)。
也可以为其他情况(最佳，平均)定义边界吗？
是的。所有情况都有其上限和下限。