ランダウの記号
Landau symbol
よく$ \Omicron(n)とか$ \Omicron(n^2)とか$ \Omicron(n\log{n})とか$ \Omicron(k^n)とか書かれるのがランダウの記号。
意味論的には、(特に極限での)関数で引数(ここでは$ n)が大きくなる時に、もっとも大きな影響を示す項を抜き出したものになる。
例えば$ f(n) = an^2 + bn + cがある時に$ \Omicron(f(n)) = \Omicron(n^2)
定数倍は無視される。
$ \Omicron(kn)=\Omicron(n)
さらに小さな項がたくさんあっても、実質的に無視する事ができるということ。
数学的にはもっと厳密な定義があるとのことだが、そのあたりは書かない。
計算機科学では、処理時間(計算量)が入力件数nに対してどれだけ増えるのかを示すのに使われる。
この時は、計算量オーダーとか、処理オーダーとか、オーダー時間とか呼ばれる。(O が Order の意味と勘違いされている模様)
記号は、いわゆる英語のアルファベットのオー(O, Unicode U+004F)、ではなく、ギリシア文字のオミクロン(Ο, Unicode U+039F)であるとのこと。見た目はまったく区別が付かない。
ランダウ自身はオミクロンとは呼んでなくて、クヌースがそう呼んだとのこと。
$ \TeXのギリシア文字では、なぜかオミクロン = O (コマンド無し。Unicode U+004F)ということになっている。
$ \TeXでは区別が付かない文字はそのまま使う方針らしい。
$ \TeX記法では \mathcal{O} と書くとよいとのこと。
$ \mathcal{O}
Scrapbox の $ \TeX記法では、\Omicron が使えた。
$ \Omicron
参考