ランダウの記号

ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （オーもしくはオミクロン Ο。数字の0ではない）を用いることから（ランダウの）O-記法、ランダウのオミクロンなどともいう。

記号 O は「程度」の意味のオーダー（Order）から。

なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。

ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。

概要

ランダウの記号

{\displaystyle f(x)=O(g(x))}

は変数 x を極限に飛ばした時の関数 f の振る舞い（漸近的挙動）を、別の関数 g を目安にして記述する目的で用いられる。

たとえば f(x) = 3x² + 4x − 5 において x を ∞ に飛ばした時の f の挙動を考えると、x が十分大きいところでは第一項がその他の項に比べて極端に大きく、二項目以降はいわば「誤差」にすぎなくなる。したがって f の挙動は「定数×x ²」とほぼ等しくなる。ランダウの O-記法を用いる事でこの事実を

{\displaystyle f(x)=O(x^{2})}

と書き表す事ができる。

このように g は f よりも簡単な関数（上の例では x²）が用いられる事が多い。

また前述の関数 f は二次関数であるので、x が十分大きいところでは x³ よりはるかに小さい。ランダウの o-記法を用いる事でこの事実を

{\displaystyle f(x)=o(x^{3})}

と書き表す事ができる。

上では x を ∞ に飛ばした時の挙動を例にとって説明したが、何らかの定数に近づけたり −∞ に飛ばした時の挙動も同様にランダウ記号で書き表せる。x をどこに飛ばしたときの話であるのかは文脈から判断するよりないが、どこに飛ばしたかを明示する為に、

{\displaystyle f(x)=O(x^{2})\;{\text{ as }}x\to \infty }

のように書き表す事もできる。

f(x) = O(g(x)), f(x) = o(g(x)) (x → ∞) はそれぞれ

·         {\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|}　が存在する場合、その値が有限であること（一般の場合は後述）

·         {\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|=0}

を表す。（厳密にはε-δ論法で定義する。）

ランダウ記法は様々な分野で有益であり、たとえば指数関数を3次までテイラー展開したものは

{\displaystyle \mathrm {e} ^{x}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+O(x^{4})\quad {\text{ as }}x\to 0}

と書き表せる。

記号 O とo は通常、関数の収束や発散の漸近的な上界を記述する為に用いられる。同様に漸近的な下界を記述する為にΩ, ωという類似記法が用いられ、上下両方を記述する為にΘ という記法を用いる。

ただし、Ω、ω、Θは主に計算機科学で用いられる記法であり、数学では O と o をこれらの意味に流用する事が多い（どの意味で用いているのかは文脈から判断）。

 

 

その他の漸近記法

O-記法と関連がある、Ω-記法、ω-記法、Θ-記法を導入する。

Ω-記法とω-記法はそれぞれ、O-記法とo-記法の定義で大小を反転させる事により得られる。Θ-記法Θ(g)は O(g) と Ω(g)を両方満たすことを意味する。

ただし、Ω-記法に関しては、この記法を初めて導入したハーディーとリトルウッド^[1]は今日のそれとは若干異なった意味に用いていたので、あわせてそれも記す。(以下の表の「HLの定義」の部分)。

今日の定義との違いの要点をかいつまんでいえば、今日の定義ではΩ-記法は前述のようにO-記法の定義の大小反転だが、ハーディー達の定義ではΩ(g)はo(g)を満たさない事として定義していた。

両者の定義は性質のよい関数、例えば多項式に対しては同値だが、極限に近づく際に振動するような関数に関しては必ずしも同値ではない。

 

 

https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7