オーダー記法を使う大まかな目的 (執筆中)

ランダウのオーダー記法とは、2つの実数関数の比較に用いられる記法である。この記事では、どのような理由でどのような特徴をもつ比較方法が必要となるかを説明し、その比較方法としてランダウのオーダー記法を紹介する。

アルゴリズム

執筆中

アルゴリズムの比較

執筆中

オーダー記法

以上をまとめると、実数関数同士の比較方法として

  • 十分に右側の領域 (つまり $x$ が十分に大きい領域) に注目し、
  • 定数倍程度の違いは無視することにした
関数同士の大小関係で比較したいということになる。そこで、2つの実数関数 $f$, $g$ を比較する方法として、オーダー記法を次のように与える。

定義 ($O$-記法) $f$, $g$ をそれぞれ実数関数とする。これらが\[\exists k\gt0:\exists x_0:\forall x\gt x_0: |f(x)|\leq k|g(x)|\]を満たすことを $f\in O(g)$ と書く。

グラフを用いた視覚的な言葉で言い換えると、$f\in O(g)$ は「ある程度以上右側の ($x$ が大きい) 領域では $|g(x)|$ の定数倍で $|f(x)|$ を上から覆うことができる」ことを意味する。つまり直感的には「 ($x$ がある程度より大きいところ限定で、定数倍も許すという条件付きではあるが) $f$ は $g$ と同程度か $g$ より小さい」と言えるだろう。ただ、いちいち括弧の中を述べるのは面倒なので、今後はその部分を『オーダー』という言葉でまとめて「$f$ のオーダーは $g$ のオーダー以下である」もしくは「$g$ のオーダーは $f$ のオーダー以上である」と表現することにする。こうすると当初の目的である大小関係っぽさが出てくるが、次回の記事で説明する通り、この関係はちゃんと大小関係っぽい性質 (前順序性) を持っている。

もう一つのオーダー記法を次のように与える。

定義 ($\Theta$-記法) $f$, $g$ をそれぞれ実数関数とする。これらが $f\in O(g)$ と $g\in O(f)$ をともに満たすことを $f\in \Theta(g)$ と書く。

上の $O$-記法の直感的表現を流用すると、$f\in \Theta(g)$ は「$f$ のオーダーは $g$ のオーダー以下であり、以上でもある」となる。少し長いが、直感的な言い換えで「$f$ のオーダーは $g$ のオーダーと同程度である」とすることができるだろう。こうすると $f$ と $g$ がある意味等しいことを表す関係に見えてくるが、次々回の記事で説明する通り、この関係は「ある意味等しい」ことを表す関係に共通する性質 (同値性) を持っている。