Big-omega notation 发音

释义 Definition

Big-omega notation（大 Ω 记号）是算法与复杂度分析中的一种渐近下界表示法：如果对足够大的输入规模 \(n\)，函数 \(f(n)\) 至少以某个常数倍的 \(g(n)\) 的速度增长，则记为
\[ f(n)=\Omega(g(n)). \]
常用来表达“运行时间/空间在最坏情况下至少不会比 \(g(n)\) 更快（更小）”。

发音 Pronunciation (IPA)

/ˌbɪɡ oʊˈmɛɡə noʊˈteɪʃən/

例句 Examples

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

Even if the average case is fast, the algorithm still has Ω(n²) time in the worst case due to nested scans.
即使平均情况很快，由于嵌套扫描，这个算法在最坏情况下仍然有 Ω(n²) 的时间下界。

词源 Etymology

“Big-omega”里的 Ω 来自希腊字母 Omega（欧米伽），在数学中常用作符号。Landau 记号（渐近记号）体系里常用 O、Ω、Θ 来描述函数增长的上界、下界与紧确界；该用法在计算机科学中被广泛采用，并通过经典算法教材与 Donald Knuth 等人的著作传播开来。

相关词 Related Words

• Asymptotic
• Big-O
• Big-Theta
• Complexity
• Landau Notation
• Lower Bound
• Order Of Growth
• Worst-Case

文学与经典作品 Literary Works

• The Art of Computer Programming — Donald E. Knuth（大量使用 Ω、O、Θ 等渐近记号讨论算法复杂度）
• Introduction to Algorithms — Cormen, Leiserson, Rivest, Stein（CLRS；在复杂度与下界分析中系统使用 Big-Ω）
• Algorithms — Robert Sedgewick & Kevin Wayne（以渐近分析讲解算法效率与下界）
• Computational Complexity: A Modern Approach — Arora & Barak（在复杂性理论中频繁使用 Ω 表达下界）
• Introduction to the Theory of Computation — Michael Sipser（在复杂度与证明中常见 Ω 记号）