Omega Notation

释义 Definition

Ω 记号（Omega notation）：在算法分析与渐近复杂度中，用来表示函数的渐近下界。也就是说，Ω(g(n)) 表示某个函数在 n 足够大时，增长速度至少像 g(n) 那么快（忽略常数因子与低阶项）。常与 O（上界）、Θ（紧确界）一起使用。（在数学里 Ω 也可作其他含义，但在计算机科学中最常见的是“下界”。）

例句 Examples

The running time is Ω(n) because we must read all the input.
运行时间是 Ω(n)，因为我们必须读完整个输入。

For comparison-based sorting, there is an Ω(n log n) lower bound in the worst case.
对基于比较的排序而言，在最坏情况下存在 Ω(n log n) 的下界。

发音 Pronunciation (IPA)

/oʊˈmeɡə noʊˈteɪʃən/

词源 Etymology

Omega 来自希腊字母 Ω（omega），传统上是希腊字母表的最后一个字母；在渐近记号里，数学家用它来表示某种“下界/最低增长量”的概念。Notation 源自拉丁语词根（与“标记、记号”相关），合起来即“用 Ω 表示的记号体系”。

相关词 Related Words

• Big-O
• Theta
• Asymptotic
• Lower Bound
• Complexity
• Worst-Case
• Time Complexity

文学与经典著作 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）——在渐近分析章节系统介绍 O、Ω、Θ 及其性质与例子。
• The Art of Computer Programming（Donald E. Knuth）——讨论算法分析、增长阶与下界思想，使用并推广渐近记号。
• Concrete Mathematics（Graham, Knuth, Patashnik）——在离散数学与渐近估计的语境中使用并解释相关记号。