ランダウの記号
ランダウの記号(ランダウのきごう、英: Landau symbol)は、主に関数の極限における漸近的な挙動を比較するときに用いられる記法である。
ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O (数字の0ではない)を用いることから(バッハマン-ランダウの)O-記法 (Bachmann-Landau O-notation)、ランダウのオミクロンなどともいう。
記号 O はドイツ語のOrdnungの頭字にちなむ。
なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。
ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。
O ( f ( n ) ) O ( g ( n ) ) = O ( f ( n ) g ( n ) ) , f ( n ) O ( g ( n ) ) = O ( f ( n ) g ( n ) ) . {\displaystyle O(f(n))O(g(n))=O(f(n)g(n)),\qquad f(n)O(g(n))=O(f(n)g(n)).}
次の多項式関数を考える
f ( x ) = 6 x 4 − 2 x 3 + 5 , g ( x ) = x 4 . {\displaystyle {\begin{aligned}f(x)&=6x^{4}-2x^{3}+5,\\g(x)&=x^{4}.\end{aligned}}}
このとき、f(x) のオーダーは O(g(x)) または O(x) である。実際、オーダーの定義からこれはある定数 Cと x0 が存在して、x0 < x なる任意の x に対し |f(x)| ≤ C |g(x)| が成り立つことを意味するが、x > 1 において
| 6 x 4 − 2 x 3 + 5 | ≤ 6 x 4 + 2 x 3 + 5 ≤ 6 x 4 + 2 x 4 + 5 x 4 ≤ 13 x 4 ≤ 13 | x 4 | {\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+2x^{3}+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&\leq 13x^{4}\\&\leq 13|x^{4}|\end{aligned}}}
ランダウの記号
f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))}
は 、x がじゅうぶん大きいとき関数 f が関数 g に比例もしくはそれ以下におさえられることを示す。
たとえば二次関数 3x + 4x + 10 が x を限りなく大きくしたときどのように増大するかを考えると、変数 x が 2 より大きければ第一項 3x が他の項より大きく、さらに大きくなるほど支配的になることがわかる。漸近解析をする上では定数倍のような詳細は必要としないことが多く、O-記法を用いると、必要な情報を
3 x 2 + 4 x + 10 = O ( x 2 ) {\displaystyle 3x^{2}+4x+10=O(x^{2})}
と端的に表すことができる。
このように関数 g としては関数 f よりも単純なもの(上の例では x)が通常用いられる。(#一般的なオーダー参照。)
一方、ランダウの記号
f ( x ) = o ( g ( x ) ) {\displaystyle f(x)=o(g(x))}
は関数 f がおおよそ関数 g 未満であることを示している。
たとえば x が十分大きいとき 3x + 4x + 10 は x と比べると小さくなり、o-記法を用いると、これを