ランダウの記号をいま一度勉強してみる

TL;DR

  • 関数の漸近的挙動を表現するためのランダウの記号をちょろっと勉強し直してみた
  • そもそも物理学者の Lev Landau が考案したものかと思っていたら、ドイツの数学者 Edmund Landau が考案したものだった。すみませんでした
  • 新しい話は特にない

きっかけは何だったのか忘れたが、計算量オーダーなどでもよく出てくるランダウの記号に関してなんとなく勉強し直してみた。

よくある説明は「f(n)f(n) なる関数で nn が十分大きい時の漸近的振る舞いを記述するもので、例えば f(n)=2n2+3n+1f(n) = 2 n^2 + 3 n + 1 である場合は O(n2)O(n^2) と書く」みたいなものである。 大体こんなものだと分かっておけば十分なので、詳しく知りたい人は自分で勉強してね、的な文言が書かれていることも多い気がする。

結論から言ってしまえばその通りで、まあそういうもんだと思っておけば十分だろう（所詮 notation の話なのでそりゃそんなもんだろという声が聞こえてきそうですが…）。 せっかくなのでもう少し詳しく見ておこう。

考案者

まずはこの記法を導入した原著って眺めたことないなと思ってググってみたら、Handbuch der Lehre von der Verteilung der Primzahlen (1909) であると知った。

ここで「え？ドイツ語？」とドキッとした。 ずっと考案者はロシアの物理学者 Lev Landau だと思い込んでいたからだ。 なぜこのような勘違いをしたままここまで来たかは定かではない。 昔誰かと話していたときに「いや〜 Landau はこういうこともやっているんだね」的な会話をして、それをそのまま引きずってしまっていたのだろう、きっと。 初めて Coleman-Weinberg potential を知ったときにてっきり Steven Weinberg の仕事だと思ってしまう的な。

ともかく、正しくはドイツの数学者 Edmund Landau が考案者だということだった。

自分がずっと使ってきた記法なのに考案者を間違えて覚えていて、慚愧に堪えません、というのがこのブログエントリで一番言いたかったことです。

ちなみに原著は無償のウェブ・マルチメディア資料のアーカイブ閲覧サービスである Internet Archive で読むことができる。 便利な時代ですね。

定義とその意味

せっかくなので原著に近い形で定義を書いておく。

まず、あまり使われない発散の上界を表現するような oo (小文字のオー) の定義から。 関数 f(n),g(n)f(n), g(n) に対して、

lim⁡n→∞∣f(n)g(n)∣=0,\begin{align} \lim_{n \rightarrow \infty} \left| \frac{f(n)}{g(n)} \right| = 0, \end{align}

が成り立つとき、以下のように表記する。

f(n)=o(g(n))  (n→∞).\begin{align} f(n) = o(g(n)) \ \ (n \rightarrow \infty). \end{align}

これは f(n)f(n) は漸近的には g(n)g(n) と比べて無視できるということを言っている。 例えば、f(n)=5log⁡n+3,g(n)=2n+10f(n) = 5 \log n + 3, g(n) = 2 n + 10 という場合、5log⁡n+3=o(2n+10) (n→∞)5 \log n + 3 = o(2 n + 10) \ (n \rightarrow \infty) と書けるということである。 実際にこういう書き方をすることはほとんどないと思う。 漸近的な振る舞いを議論する上では leading term 以外や定数倍は特に意味がない場合も多い。 そのような場合、この例はもっと簡単化してしまって log⁡n=o(n) (n→∞)\log n = o(n) \ (n \rightarrow \infty) としてしまっても情報量は変わらないため、このような形で目にすることがほとんどだと思う。

ここまでは陽に n→∞n \rightarrow \infty と無限大に飛ばすことを記載していたが、これは省略されて文脈で読み取ってくれという場合が多い。 プログラミングでは入力サイズが大きくなった時の計算量オーダーを求めたいことが多いのでその場合は無限大に飛ばすが、機械学習を含めれば Taylor 展開で 0 やある特定の値に飛ばすということも出てくる。 少し慣れれば文脈を取り違えることはないと思うが、計算量オーダーでしか使ったことない人が後者の使い方を見ると混乱するかもしれない。

次によく使う OO (大文字のオー) の定義を見る。 これのみを使う場合が多いので、ランダウのビッグオー記法と言ってしまうことも多い。 関数 f(n),g(n)f(n), g(n) に対して、

lim⁡n→∞∣f(n)g(n)∣<∞,\begin{align} \lim_{n \rightarrow \infty} \left| \frac{f(n)}{g(n)} \right| < \infty, \end{align}

が成り立つとき、以下のように表記する。

f(n)=O(g(n)).\begin{align} f(n) = O(g(n)). \end{align}

無限大より小さいという書き方をしているが、これは何かしらの値が存在してそれが有限であるという意味である。 これは例をいくつかまとめて出しておく。

n+1=O(n)  (n→∞),nlog⁡n+3n+5=O(nlog⁡n)  (n→∞),en=1+n+n22!+O(n3)  (n→0),nsin⁡(n)=O(n)  (n→∞),ein=O(1)  (n→∞),1n2=O(1n3/2)  (n→∞),1n3/2=O(1n2)  (n→0),n=O(n1/2)=O(n)=o(n)  (n→∞).\begin{align} n + 1 &= O(n) \ \ (n \rightarrow \infty), \\ n \log n + 3 n + 5 &= O(n \log n) \ \ (n \rightarrow \infty), \\ e^n &= 1 + n + \frac{n^2}{2!} + O(n^3) \ \ (n \rightarrow 0), \\ n \sin (n) &= O(n) \ \ (n \rightarrow \infty), \\ e^{in} &= O(1) \ \ (n \rightarrow \infty), \\ \frac{1}{n^2} &= O \left( \frac{1}{n^{3/2}} \right) \ \ (n \rightarrow \infty), \\ \frac{1}{n^{3/2}} &= O \left( \frac{1}{n^2} \right) \ \ (n \rightarrow 0), \\ \sqrt{n} &= O(n^{1/2}) = O(n) = o(n) \ \ (n \rightarrow \infty). \end{align}

下の 3 つは定義からは正しいが殆ど使われない書き方をしている。 例えば一番下の例だと、最初の関係式はよく使う形だが、その後ろ 2 つのように書くことは殆どない。 正しいのは正しいが、ハッキリと漸近的な振る舞いが n1/2n^{1/2} と分かっているので、それよりも次数の大きいもので抑えても弱い statement になるだけで嬉しくないためである。

ということで、よく見かける OO (ビッグオー記法) だけ知っておけばまあ十分というお話でした。

まとめ

特に新しいことはないのだが、ランダウの記法を振り返ってみた。 ちゃんと考案者を覚えました。 極限だから真面目に数学的にやるならイプシロンデルタ的にやるということになりますが、この手の話でそこまでする必要はないでしょう。