Big-Omega

释义 Definition

Big-Omega（大 Ω 记号）：在算法与复杂度分析中表示渐近下界。若 \(f(n)\in \Omega(g(n))\)，意思是当 \(n\) 足够大时，\(f(n)\) 的增长速度至少与 \(g(n)\) 同阶（不低于某个常数倍的 \(g(n)\)）。常用于描述算法在最坏/平均情况下的最低可能增长级别。（该符号也常写作 Ω。）

发音 Pronunciation (IPA)

/b ome/

例句 Examples

The running time is big-omega of n.
运行时间是 \(n\) 的大 Ω 级别（至少与 \(n\) 同阶）。

For any comparison-based sorting algorithm, the worst-case time is big-omega of n log n.
对于任何基于比较的排序算法，其最坏情况下的时间复杂度都有 \(n\log n\) 的大 Ω 下界。

词源 Etymology

Omega（Ω）来自希腊字母表的最后一个字母 Ω。在渐近分析里，人们用 O（大 O）表示上界、用 Ω（大 Ω）表示下界、用 Θ（大 Θ）表示紧确界；这一套记号体系与近代数学中用于描述增长率/误差项的符号传统相关，后来被计算机科学广泛采用来讨论算法复杂度。

相关词 Related Words

• Big-O
• Big-Theta
• Asymptotic
• Lower-Bound
• Complexity
• Runtime

文学与经典作品 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在渐近符号章节系统使用 O、Ω、Θ 讨论算法上界与下界。
• The Art of Computer Programming（Donald E. Knuth）：在分析算法与渐近估计时频繁使用相关增长记号与下界论证。
• Algorithms（Robert Sedgewick & Kevin Wayne）：介绍复杂度分析与排序下界时常出现 Ω(n log n) 等表述。
• Computers and Intractability（Garey & Johnson）：复杂度理论与归约讨论中常用下界记号来刻画问题难度。