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”一書。