Big-O

定义 Definition

Big-O（大 O 记号）：用于描述算法或函数在输入规模增大时的增长上界，常用来表达时间复杂度或空间复杂度的数量级（例如 **O(n)、O(n log n)、O(n²)**）。它强调“随着 n 变大，增长趋势如何”，而不是精确常数。

例句 Examples

Big-O tells you how an algorithm’s running time grows as the input gets larger.
Big-O 用来说明当输入变大时，算法运行时间如何增长。

Although two implementations may be fast on small inputs, Big-O analysis helps compare their scalability by focusing on the dominant term and ignoring constant factors.
即使两种实现对小输入都很快，Big-O 分析仍能通过关注主导项并忽略常数因子来比较它们的可扩展性。

发音 Pronunciation (IPA)

/ˌbɪɡ ˈoʊ/

词源 Etymology

“Big-O”中的 O 来自数学中的字母 O（源自德语数学传统），与“阶（order）/数量级”相关，用来表示函数增长的上界。该记号在 19 世纪的数论与分析中逐步成形，后来被计算机科学广泛采用，用于描述算法复杂度。

相关词 Related Words

• Complexity
• Algorithm
• Asymptotic
• Upper Bound
• Theta Notation
• Big-Omega
• Big-Theta
• Runtime
• Scalability

文学与经典著作中的用例 Literary / Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：大量使用 Big-O 来分析算法时间与空间复杂度。
• The Art of Computer Programming（Donald E. Knuth）：在算法与分析章节中系统讨论渐近记号（含 Big-O）。
• Concrete Mathematics（Graham, Knuth, Patashnik）：在数学推导与渐近分析中频繁使用 Big-O。
• Structure and Interpretation of Computer Programs（Abelson, Sussman）：在讨论计算过程与效率时涉及复杂度与渐近思想。