algorithm - 最坏情况分析是否不等于渐近界限

Question

有人可以向我解释为什么这是真的吗？我听一位教授提到这是他的讲座

Answer 1

这两个概念是正交的。

您可以最坏情况渐近。如果 f(n) 表示输入 n 的给定算法所用的最坏情况时间，您可以有例如。 f(n) = O(n^3) 或最坏情况时间复杂度的其他渐近上限。

同样，您可以有 g(n) = O(n^2 log n) 其中 g(n) 是同一算法所用的平均时间(比如)大小为 n 的均匀分布(随机)输入。

或者你可以有 h(n) = O(n) 其中 h(n) 是同一算法所用的平均时间，具有特别分布的随机输入大小 n(例如，排序算法的几乎排序序列)。

渐近符号是一种“度量”。您必须指定要计算的内容:最坏情况、最佳情况、平均值等。

有时，您有兴趣说明(比方说)最坏情况复杂性的渐近下界。然后你写 f(n) = Omega(n^2) 来说明在最坏的情况下，复杂度至少 n^2。 big-Omega 表示法与 big-O 相反:f = Omega(g) 当且仅当 g = O(f)。