Big Omega

Definition / 释义

Big Omega（大Ω记号，Ω）是算法与计算复杂度分析中的一种渐近下界表示法：若函数 (f(n)) 的增长速度在足够大的 (n) 上至少像 (g(n)) 那样快，则写作
[ f(n) = \Omega(g(n)). ]
常用来表达“最少需要这么多时间/空间”。（在数学里 Ω 也可能有其他含义，但计算机科学中最常见的是“渐近下界”。）

Pronunciation / 发音（IPA）

/ˌbɪɡ oʊˈmeɡə/

Examples / 例句

For comparison-based sorting, the time complexity is Ω(n log n).
对于基于比较的排序算法，时间复杂度下界是 Ω(n log n)。

Although the average case may be faster, the algorithm still has an Ω(n²) worst-case running time on adversarial inputs.
尽管平均情况可能更快，但在对抗性输入下，该算法的最坏运行时间仍然有 Ω(n²) 的下界。

Etymology / 词源

“Big Omega”里的 Omega（Ω）来自希腊字母表的最后一个字母“ω/Ω”。在渐近符号体系中，它与 Big O（O）、Big Theta（Θ）并列，形成一套用希腊字母表示增长阶（Landau 记号）的传统；其中 Ω被约定用来表示“从下方界定”的增长速度（下界）。

Related Words / 相关词汇

• Asymptotic
• Big O
• Big Theta
• Complexity
• Lower Bound
• Landau Notation
• Omega Notation
• Worst Case

Literary Works / 文献与名著中的使用

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein），常用 Ω 记号讨论排序下界、递归式与渐近分析。
• The Art of Computer Programming（Donald E. Knuth），在算法分析与渐近估计中系统使用 Landau 记号（含 Ω）。
• Introduction to the Theory of Computation（Michael Sipser），在复杂度与可计算性相关章节中使用渐近符号讨论时间下界。