Big-Omega 表示法

Ω-表示法用于渐近下界。

正式定义

让 f(n) 和 g(n) 是在正实数集上定义的两个函数。如果有正常数 c 和 n0，我们写 f(n) = Ω(g(n))，这样：

0 ≤ c g(n)≤f(n) for all n ≥ n0。

笔记

f(n) = Ω(g(n)) 意味着 f(n) 渐渐渐渐渐渐变慢而不是 g(n)。当算法分析不足以说明Θ(g(n)) 或/和 O(g(n)) 时，我们也可以说Ω(g(n))。

从符号的定义遵循定理：

对于两个任何函数 f(n) 和 g(n) 我们有 f(n) = Ө(g(n)) 当且仅当 f(n) = O(g(n)) and f(n) = Ω(g(n))。

图形Ω表示法可表示如下：

例如，让我们有 f(n) = 3n^2 + 5n - 4。然后 f(n) = Ω(n^2)。它也是正确的 f(n) = Ω(n)，甚至是 f(n) = Ω(1)。

另一个解决完美匹配算法的例子：如果顶点数是奇数，则输出 No Perfect Matching，否则尝试所有可能的匹配。

我们想说算法需要指数时间，但事实上你不能使用Ω的通常定义来证明Ω(n^2) 的下限，因为算法在 n 个奇数的线性时间内运行。我们应该通过说一些不变的 c>0，f(n)≥ c g(n) 来定义 f(n)=Ω(g(n))。这给出了上下界之间的良好对应关系：f(n)=Ω(g(n)) iff f(n) != o(g(n))。

参考

正式定义和定理取自“Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein .The Introduction to Algorithms”一书。