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\) 记号。