手帳と試行

計算量の理論で頻繁に登場するビッグオー記法を導入する。

目次

ざっくりとした定義 ビッグオー記法 ビッグオメガ記法 ビッグシータ記法 注意 具体的な使い方の例 より厳密な定義 別の理解

まずはざっくりと定義を説明する。

以下、実数を入力して実数を出力する関数 $f: \R \to \R$ を考える。

The big-$\mathcal O$ notation

関数の入力値 $x$ が十分に大きい場合に、有限確定値 $M$ が存在して

$\begin{aligned} |f(x)| \le M |g(x)| \end{aligned}$

が成り立つことを

$\begin{aligned} f(x) ={}& \mathcal O(g(x))~(x \to \infty), \\ f(x) \le{}& \mathcal O(g(x)), \\ f(x) \in{}& \mathcal O(g(x)) \\ \end{aligned}$

などと表す。

このような表現方法は $x \to \infty$ のみならず、定数 $a$ に対して $x \to a$ であるような場合に対しても定義することができる。

The big-$\mathcal O$ notation

関数の入力値 $x$ が限りなく定数 $a$ に近づく際に、有限確定値 $M$ が存在して

$\begin{aligned} |f(x)| \le M |g(x)| \end{aligned}$

が成り立つことを

$\begin{aligned} f(x) ={}& \mathcal O(g(x))~(x \to a) \end{aligned}$

などと表す。

以上のような表記をビッグオー記法 (Big-$\mathcal O$ notation) という。

The big-$\Omega$ notation

関数の入力値 $x$ が十分に大きい場合に、有限確定値 $m$ が存在して

$\begin{aligned} |f(x)| \ge m |g(x)| \end{aligned}$

が成り立つことを

$\begin{aligned} f(x) ={}& \Omega(g(x))~(x\to\infty), \\ f(x) \ge{}& \Omega(g(x)), \\ f(x) \in{}& \Omega(g(x)) \end{aligned}$

などと表す。

ビッグオー記法とは不等号の向きが反対であることに注意しよう。ビッグオー記法と同様に、$x \to \infty$ のみならず定数 $a$ に対して $x \to a$ であるような場合に対しても定義することができる。

The big-$\Omega$ notation

関数の入力値 $x$ が限りなく定数 $a$ に近づく際に、有限確定値 $m$ が存在して

$\begin{aligned} |f(x)| \ge m |g(x)| \end{aligned}$

が成り立つことを

$\begin{aligned} f(x) ={}& \Omega(g(x))~(x \to a) \end{aligned}$

などと表す。

以上のような表記をビッグオメガ記法 (Big-$\Omega$ notation) という。

ビッグオー記法による $g(x)$ と、ビッグオメガ記法による $g(x)$ が一致する場合には、しばしば

などと表される。この表記をビッグシータ記法という。

等号により表現されていることからしばしば混乱を招く。たとえば

ではあるが、

ではない。また、通常は $x\to\infty$ などは省略して

などと表現されるため、それが $x \to \infty$ なのか $x \to 0$ なのかは状況に応じて判断する必要がある。

1. 入力が大きくなった場合の関数値の振る舞いを記述する
   $\begin{aligned} 2 \log n \in{}& \mathcal O(n^2),\\ 2 \log n \in{}& \mathcal O(\log n),\\ 2 \log n \in{}& \Theta(\log n),\\ 2 \log n \in{}& \Omega(\log n),\\ 2 \log n \in{}& \Omega(1) \end{aligned}$

   以上のことから確認できるように、ビッグオー記法やビッグオメガ記法はそれぞれ関数の近似的な上界と下界を記すものであり、ビッグシータ記法に近いものほど意味を成す。

2. 無限級数の振る舞いを記述する

   指数関数を3次の項までマクローリン展開すると

   $\exp(x) = 1 + \frac{1}{1!}x + \frac{1}{2!}x^2 + \frac{1}{3!}x^3 + \mathcal O(x^4)~(x \to 0)$
3. アルゴリズムの性能の限界を理論的に記述する

   多腕バンディット問題に対し、期待リグレット $\mathrm{E} [\mathop{\rm regret}(n)]$ を最小化するというアプローチを取る場合、第 $N$ 回目の試行における期待リグレット $\mathrm{E} [\mathop{\rm regret}(N)]$ の下界は

   $\mathrm{E} [\mathop{\rm regret}(N)] = \Omega(\log N) ~ (N \to \infty)$

   であることが知られている。

より厳密には、イプシロン-デルタ論法を用いて次のように定義する。

The big-$\mathcal O$ notation and the big-$\Omega$ notation

$\begin{aligned} &f(x) = \mathcal O(g(x)) ~ (x \to \infty) \\ &\qquad\overset{\rm def}\iff {}^\forall x_0\gt0,~ {}^\exists M\gt0,~ \left[ x \gt x_0 \implies |f(x)| \le M|g(x)| \right] \\ \\ &f(x) = \mathcal O(g(x)) ~ (x \to a) \\ &\qquad\overset{\rm def}\iff {}^\forall x_0\gt0,~ {}^\exists M\gt0,~ \left[ |x - a| \lt x_0 \implies |f(x)| \le M|g(x)| \right] \\ \\ &f(x) = \Omega(g(x)) ~ (x \to \infty) \\ &\qquad\overset{\rm def}\iff {}^\forall x_0\gt0,~ {}^\exists m\gt0,~ \left[ x \gt x_0 \implies |f(x)| \ge m|g(x)| \right] \\ \\ &f(x) = \Omega(g(x)) ~ (x \to a) \\ &\qquad\overset{\rm def}\iff {}^\forall x_0\gt0,~ {}^\exists m\gt0,~ \left[ |x - a| \lt x_0 \implies |f(x)| \ge m|g(x)| \right] \end{aligned}$

十分大きな $x$ に対して $g(x) \gt 0$ が成り立つ場合には、次のように書き換えることができる。