Landau Notation

释义 Definition

Landau notation（兰道记号）是一组用于描述函数在某个极限（常见为 (n\to\infty) 或 (x\to 0)）下“增长/衰减速度”的渐近记号。最常见的包括 (O(\cdot))（大 O）、(o(\cdot))（小 o）、(\Theta(\cdot))、(\Omega(\cdot)) 等，广泛用于算法复杂度分析与数学中的渐近估计。
（在不同领域也可能强调不同子集，例如分析数论中常用 (O) 与 (o)。）

发音 Pronunciation (IPA)

/ˈlænd.aʊ noʊˈteɪ.ʃən/

例句 Examples

Landau notation helps us describe how fast an algorithm grows.
兰道记号帮助我们描述算法的增长速度。

Using Landau notation, we can write (f(n)=O(n\log n)) to express an asymptotic upper bound as (n\to\infty), while (f(n)=o(n)) indicates the growth is strictly smaller than linear.
用兰道记号，我们可以写 (f(n)=O(n\log n)) 来表示当 (n\to\infty) 时的渐近上界，而 (f(n)=o(n)) 则表示其增长严格小于线性。

词源 Etymology

“Landau”来自德国数学家 Edmund Landau（埃德蒙·兰道） 的姓氏。兰道在19世纪末至20世纪初的分析数论研究中系统使用并推广了这些渐近记号，因此后人把这一套记号统称为 Landau notation。“notation”意为“记号/符号体系”。

相关词 Related Words

• Big-O Notation
• Little-o
• Big-Theta
• Big-Omega
• Asymptotic
• Complexity
• Order
• Growth Rate

文学与经典著作 Literary Works

• Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen（《素数分布理论手册》）——分析数论中大量使用 (O)、(o) 等渐近记号。
• Donald E. Knuth, The Art of Computer Programming（《计算机程序设计艺术》）——用渐近记号讨论算法与计算过程的增长阶。
• Thomas H. Cormen et al., Introduction to Algorithms（《算法导论》）——系统讲解大 O / (\Theta) / (\Omega) 等（常与“Landau 记号”并称或归入同一体系）。
• G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers（《数论导引》）——在估计与定理陈述中频繁出现 (O) 与 (o) 记号。