Big-O Notation

释义 Definition

大 O 记号：用于描述算法在输入规模趋于无穷大时的渐近上界（增长速度的上限），常用来表达时间复杂度或空间复杂度的数量级，如 **O(n)、O(n log n)、O(n²)**。它强调“增长趋势”，通常忽略常数因子与低阶项。（也存在其他相关记号如 Θ、Ω 等，用于更精确或不同方向的界。）

发音 Pronunciation (IPA)

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

例句 Examples

Big-O notation helps compare how fast algorithms grow as input size increases.
大 O 记号帮助比较算法在输入规模增大时增长得有多快。

Although the code has several constant-time checks, its overall runtime is O(n log n) because sorting dominates.
尽管代码里有好几个常数时间的检查，但整体运行时间是 O(n log n)，因为排序步骤占主导。

词源 Etymology

“Big-O”中的 O 源自德语词 Ordnung（意为“阶/数量级/秩序”），由数论学家保罗·巴赫曼（Paul Bachmann）在 19 世纪末使用，后由埃德蒙·兰道（Edmund Landau）推广，因此也常称为巴赫曼–兰道记号（Bachmann–Landau notation）。用于用简洁符号表达函数增长的“阶”。

相关词 Related Words

• Algorithm
• Complexity
• Time Complexity
• Space Complexity
• Asymptotic
• Theta Notation
• Omega Notation
• Order Of Growth
• Worst-Case
• Upper Bound

文学与著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：用 Big-O 系统化分析算法时间复杂度。
• The Art of Computer Programming（Donald E. Knuth）：大量使用渐近记号讨论算法与数列的增长阶。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在排序、查找等章节频繁用 Big-O 说明性能差异。
• Concrete Mathematics（Graham, Knuth, Patashnik）：在离散数学与算法分析的推导中使用 Big-O/Θ 等记号。