基本的な関数のオーダー

ランダウのオーダー記法とは、関数を比較する方法である。ここでは、諸々の初等関数についてどのようにオーダー表記できるかを論じる。

オーダーの定義と諸性質

ここでは前回までと同様の定義を用いる。

定義$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)$ と $g\in O(f)$ をともに満たすことを $f\in \Theta(g)$ と書く。

より簡素に書けば\begin{eqnarray} f \in O(g) & \Leftrightarrow & \exists k \gt 0, \exists x_0, \forall x \gt x_0, |f(x)| \leq k |g(x)|\\ f \in \Theta(g) & \Leftrightarrow & f \in O(g) \land g \in O(f). \end{eqnarray}ということだ。

前回までで確認したように、$f\in O(g)$ を「$f$ のオーダーは $g$ のオーダー以下である」と言い、$f\in\Theta(g)$ を「$f$ のオーダーと $g$ のオーダーは同程度である」と言う。

これらの記法について前回まででその性質を確認したが、その中でも推移性と対称性はこの記事でも用いる重要な性質である。証明は前回までの記事を見ればよいとして、ここでは推移性を持つという事実を再び述べておく。

定理$f$, $g$, $h$ を実数関数とする。このとき

  1. (推移性) $f\in O(g)$, $g\in O(h)$ ならば $f\in O(h)$ であり、
  2. (推移性) $f\in \Theta(g)$, $g\in \Theta(h)$ ならば $f\in \Theta(h)$ であり、
  3. (対称性) $f\in\Theta(g)$ ならば $g\in\Theta(f)$ である。

多項式関数のオーダー

もっとも単純な関数は、有限回の四則演算のみで表すことができる多項式関数であろう。もっと厳密には、$f$ が多項式関数であるとは、ある非負整数 $d$ と実数列 $c_0,c_1,\dots,c_d$ が存在して $f(x)=\sum^d_{i=0} c_ix^i$ と表すことができることを言う。そして、この表し方をしたときに $c_d\neq 0$ となっていれば、$d$ を $f$ の次数と呼び、$f$ は $d$ 次多項式関数である。たとえば $f(x)=2x^2 + 3$($=2x^2+0x+3$) は 2 次多項式関数である。

多項式関数は次の定理が示すように、より簡単な多項式関数 $x^n$ でオーダー表記することができる。

定理次数 \(d\) の実数関数 \(f(x)=\sum^d_{i=0} c_ix^i\), \(c_d \neq 0\)において、

  1. \(n\geq d\) ならば \(f\in O(x^n)\)
  2. \(0\leq n\leq d\) ならば \(x^n \in O(f)\)
  3. \(f \in \Theta(x^d)\)
  4. \(n\gt d\) ならば \(x^n \not\in O(f)\)
  5. \(0\leq n\lt d\) ならば \(f\not\in O(x^n)\)

(証明) まず(i)を示す。\(k=\sum^d_{i=0}|c_i|\), \(x>1\)とすると、\(k>0\)であり、 \begin{eqnarray} |f(x)| &=& \left| \sum^d_{i=0} c_ix^i \right| \\ &\leq& \sum^d_{i=0} |c_ix^i| \\ &=& \sum^d_{i=0} |c_i||x^i| \\ &\leq& \sum^d_{i=0} |c_i||x^d| \\ &=& k|x^d| \\ &\leq& k|x^n| \end{eqnarray} より、\(f \in O(x^n)\)。

次に、(ii) を \(d\) についての数学的帰納法で示す。\(d=0\) のとき、\(n=0\), \(f(x)=c_0\) であり \begin{eqnarray} &&|c_0|^{-1} \gt 0, \\ &&\forall x \gt 0:\; |x^0| \leq |c_0|^{-1}|f(x)| \end{eqnarray} より、\(x^0=x^n\in O(f)\)。

\(d\geq 1\) であり \(d-1\) 次の多項式関数については成り立つとする。このとき、\(f(x)=xf'(x)+c_0\) とすると、$f'$ は $d-1$ 次の多項式関数であるので、ある \(k'\gt 0\), \(x_0'\) が存在して \[\forall x\gt x_0':\;|x^{d-1}|\leq k'|f'(x)|.\] また、三角不等式より\begin{eqnarray}|f(x)| &=& |xf'(x)+c_0| \\ &\geq& |f'(x)||x|-|c_0|.\end{eqnarray}ここで、\(x_0 = \max\{1, x_0', 2k'|c_0| \}\) と定めて \(x\gt x_0\) とすると\begin{eqnarray}&&|f'(x)||x|-|c_0| \\ &\geq& k'^{-1}|x^{d-1}||x|-|c_0| \\ &\geq& k'^{-1}|x^d|-|c_0|.\end{eqnarray}ここで、\( x^d\geq x \geq 2k'|c_0| \) より \( |c_0|\leq \frac{1}{2k'}|x^d| \) であるので \begin{eqnarray} && k'^{-1}|x^d|-|c_0|\\ &\geq& \frac{1}{k'}|x^d|-\frac{1}{2k'}|x^d| \\ &=& \frac{1}{2k'}|x^d|\\ &\geq& \frac{1}{2k'}|x^n|.\end{eqnarray}以上より、\(k=2k'\gt 0\), \(x_0 = \max\{1, x_0', 2k'|c_0| \}\) に対して\[\forall x\gt x_0:\;|x^n|\leq k|f(x)|.\]

(iii)は、(i)および(ii)について\(n=d\) とした系から導かれる。

(iv) を背理法で示す。$x^n\in O(f)$ と仮定する。このとき $n\gt d$ より $n-1\geq d$ であるので (i) より $f\in O(x^{n-1})$。したがって $O$-記法の推移性より $x^n \in O(x^{n-1})$ となるが、$\forall x>1:|x^n|\gt |x^{n-1}|$ よりこれは誤りである。よって仮定 $x^n\in O(f)$ は誤りである。

(v) を背理法で示す。\(f\in O(x^n)\) と仮定する。$n\lt d$ より $n+1\leq d$ であるので (ii) より $x^{n+1}\in O(f)$。したがって $O$-記法の推移性より $x^{n+1} \in O(x^n)$ となるが、$\forall x>1:|x^{n+1}|\gt |x^n|$ よりこれは誤りである。よって仮定 $f\in O(x^n)$ は誤りである。

この定理は任意の多項式関数 $f$ を簡単な多項式関数 $x^n$ と比較するものであるが、この定理とオーダーの推移性を用いることで、任意の2つの多項式関数 $f$ と $g$ を比較することもできる。

定理次数 \(d\) の多項式関数 $f$ と次数 \(d'\) の多項式関数 $g$ において、

  1. \(d\lt d'\) ならば \(f\in O(g)\) であり \(g\not\in O(f)\),
  2. \(d=d'\) ならば \(f \in \Theta(g)\).

(証明) まず (i) の \(f\in O(g)\) を示す。定理より $f\in O(x^d)$。さらに定理と $d\lt d'$ より $x^d\in O(g)$。以上のことから $O$-記法の推移性より $f\in O(g)$。

次に (i) の \(g\not\in O(f)\) を背理法で示す。定理より $x^{d'}\in O(g)$ である。ここで \(g\in O(f)\) を仮定すると $O$-記法の推移性より $x^{d'}\in O(f)$ となるが、これは $d'\gt d$ より定理に矛盾するので仮定の \(g\in O(f)\) は誤りである。

(ii) を示す。$d=d'$ と定理より $f\in\Theta(x^d)$, $g\in\Theta(x^d)$ であり、 $\Theta$-記法の対称性と推移性より $f\in\Theta(g)$。

この定理から、多項式関数同士のオーダーは必ず比較でき、その大小は次数の大小と一致することがわかる。

指数関数のオーダー

次に、指数関数のオーダーを測る。まず、指数関数同士を比較したときのオーダーはどうだろうか。直感的には $2^x$ と $3^x$ のオーダーは同程度であり $2^x\in\Theta(3^x)$ のように感じられるかもしれないが、以下の定理が示すようにこれは誤りである。

定理$a>b>0$ とする。このとき $a^x \not\in O(b^x)$。

(証明) $k>0$, $x_0$ を実数とし、\[|a^x|\gt k|b^x|\]を満たす実数 $x>x_0$ が存在することを示す。ここで $x$ を\[x=\max\left\{x_0,\;\frac{\log_b k}{-1+\log_b a}\right\}+1\]と定める。このとき、$x>\log_b k/(-1+\log_b a)$, $-1+\log_b a \gt 0$ であるから $x\log_b a \gt x+\log_b k$ である。したがって\begin{eqnarray}|a^x| &=& a^x \\ &=& b^{x\log_b a}\\ &\gt& b^{x+\log_b k}\\ &=& kb^x\\ &=& k|b^x|.\end{eqnarray}

この定理より $3^x \in O(2^x)$ は成立せず、したがって $2^x\in\Theta(3^x)$ でもない。

次に、多項式関数と指数関数を比較することを考えると次の定理が得られる。

定理$b$ を正の実数とし、$n$ を非負整数とすると

  1. $b \gt 1$ ならば $x^n \in O(b^x)$, $b^x \not\in O(x^n)$,
  2. $b \lt 1$ ならば $b^x \in O(x^n)$, $x^n \not\in O(b^x)$.

(証明) まず 1 を示す。指数関数のマクローリン展開より\[b^x = \sum^{\infty}_{i=0} \frac{1}{i!} (x\log b)^i\]であり、この第 $n+1$ 項までに当たる部分を取り出して\[f(x) = \sum^{n+1}_{i=0} \frac{1}{i!} (x\log b)^i \]とすると、$x\gt 0$ であれば $b\gt 1$ より $x\log b \gt 0$ であるので\[0\leq f(x)\leq b^x\]であり、定理よりある実数 $k\gt 0$, $x_0'$ が存在して\[\forall x\gt x_0':\; |x^n|\leq k|f(x)|.\] 以上より $x_0 = \max\{0,x_0'\}$ とすると\begin{eqnarray}\forall x\gt x_0:\;|x^n|&\leq& kb^x \\ &=& k|b^x|\end{eqnarray}であるので $x^n \in O(b^x)$。

ここで $b^x \in O(x^n)$ と仮定すると次のように矛盾する。まず上の議論から $f\in O(b^x)$ である。このとき仮定と $O$-記法の推移性より $f\in O(x^n)$ となるが $f$ は $n+1$ 次式であるので定理に矛盾する。よって $b^x \in O(x^n)$ ではない。

次に 2 を示す。0次関数 $f(x)=1$ を考えると定理より $1\in O(x^n)$ であり、$0\lt b\lt 1$ より 任意の $x\gt 0$ に対して\begin{eqnarray}|b^x|&=&b^x \\ &\leq& 1^x\\  &=& |1|\end{eqnarray}であるので $b^x\in O(1)$。したがって $O$-記法の推移性より $b^x\in O(x^n)$。

ここで $x^n \in O(b^x)$ と仮定すると、$b^x\in O(1)$ と $O$-記法の推移性より $x^n \in O(1)$ となるが 1 は0次の多項式関数であるので定理に矛盾する。したがって $x^n \in O(b^x)$ ではない。

この定理を一般の多項式関数に対しても述べることができる。

定理$b$ を正の実数とし、$f$ を $d$ 次の多項式関数とする。このとき

  1. $b\gt 1$ ならば $f\in O(b^x)$, $b^x\not\in O(f)$
  2. $b\lt 1$ ならば $b^x\in O(f)$, $f\not\in O(b^x)$

(証明) まず 1 を示す。定理より $f \in O(x^d)$ であり定理より $x^d\in O(b^x)$ であるので $O$-記法の推移性より $f\in O(b^x)$。また、定理より $f \in O(x^d)$ であるので $b^x \in O(f)$ と仮定すると $O$-記法の推移性より $b^x\in O(x^d)$ となって定理に矛盾するので、仮定は誤りであり $b^x\not\in O(f)$。

次に 2 を示す。定理より $x^d\in O(f)$ であり定理より $b^x\in O(x^d)$ であるので $O$-記法の推移性より $b^x\in O(f)$。また、定理より $x^d \in O(f)$ であるので $f\in O(b^x)$ と仮定すると $O$-記法の推移性より $x^d\in O(b^x)$ となって定理に矛盾するので、仮定は誤りであり $f\not\in O(b^x)$。

以上の定理から、底が1を超える指数関数のオーダーはあらゆる多項式関数よりも大きく、底が1未満の指数関数のオーダーはあらゆる多項式関数 (ただし定数関数 0 を除く) よりも小さいとわかる。