Big O

释义 Definition

Big O（大 O 记号）：用于描述算法或函数在输入规模增大时的增长上界（常指时间复杂度或空间复杂度），强调“规模趋于无穷大时的主要增长趋势”，忽略常数与低阶项。也常泛指“复杂度等级”（如 *O(n)、O(n log n)、O(n²)*）。

发音 Pronunciation

/ˌbɪɡ ˈoʊ/

例句 Examples

Big O helps me estimate how fast an algorithm is.
Big O 帮助我估算一个算法有多快。

Although both solutions work, the second one has better Big O behavior as the dataset grows, because it runs in O(n log n) instead of O(n²).
虽然两种方案都能用，但当数据集变大时，第二种方案的 Big O 表现更好，因为它是 O(n log n) 而不是 O(n²)。

词源 Etymology

Big O 来自数学中的Landau 记号（Landau notation），由德国数学家 Edmund Landau 推广，用字母 O 表示“数量级/阶（order）”的上界概念。后来在计算机科学中被广泛用于刻画算法复杂度，因此常以 “Big O” 的称呼出现。

相关词 Related Words

• Asymptotic
• Complexity
• Runtime
• Time
• Space
• Upper Bound
• Theta Notation
• Big Omega
• Big Theta

文学与著作中的用例 Literary Works

• Introduction to Algorithms（《算法导论》，Cormen/Leiserson/Rivest/Stein）——用 Big O 系统讲解渐近复杂度与算法分析。
• The Art of Computer Programming（《计算机程序设计艺术》，Donald E. Knuth）——讨论算法分析与渐近记号（含 Big O 的思想与用法）。
• Concrete Mathematics（《具体数学》，Graham/Knuth/Patashnik）——在离散数学与算法分析语境中使用渐近记号（含 Big O）。