对于算法来说，界限与最佳/最差情况有何关系？最坏情况与上限同义，最好情况与下限同义吗？或者你至少可以从另一个中衍生出一个吗？或者它们根本没有关系？
最佳答案
是的，它可能意味着最坏情况与上限同义，最佳情况与下限同义。
最坏情况性能在算法分析中使用最多。在最坏情况分析中，我们保证算法运行时间的上限，这是很好的信息。换句话说，我们必须找到导致执行次数最多的操作的执行。 在最佳情况分析中，我们计算算法运行时间的下限。我们必须知道导致执行最少操作数的情况。
关于你的最后一个问题，是的，我们可以使用平均情况指标来压缩/解决最坏情况或最好情况。 设 O、θ、Ω 分别代表最坏情况、平均情况和最好情况，f(n) 和 g(n) 为两个任意函数。
1) 如果 f(n) = O(g(n)) 且 f(n) = θ(g(n)) ==> f(n) = Ω(g(n))
2) 如果 f(n) = Ω(g(n)) 且 f(n) = θ(g(n)) ==> f(n) = O(g(n))
关于算法、上限/下限以及最佳/最差情况，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30967044/