14.7 漸近記法

漸近記法は関数 \(f(n)\) の \(n\) が大きくなるときの振る舞いに関する簡単な指標を与えるために利用される。例えば、漸近等価性を表す二項関係 \(\sim\) (定義 14.4.2) は二つの関数が同じ速さで大きくなることを意味する。このほかにも、ある関数が別の関数より格段に遅く大きくなることを示す「リトルオー」や、ある関数が別の関数と同程度に速く大きくなることを示す「ビッグオー」といった二項関係が存在する。

14.7.1 リトルオー

定義 14.7.1

二つの関数 \(f, g \colon \mathbb{R} \to \mathbb{R}\) があり、\(g\) が非負だとする。\(f = o(g)\) と表記される二項関係を次のように定義する:

\[ f = o(g) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \lim_{x \to \infty} \frac{f(x)}{g(x)} = 0 \]

この記法をリトルオー記法 (little-o notation) と呼ぶ。\(f = o(g)\) が成り立つとき、\(f\) は \(g\) より漸近的に小さい (asymptotically smaller) と言う。

例えば次の関係からは \(1000x^{1.9} = o(x^{2})\) が分かる:

\[ \lim_{x \to \infty} \frac{1000 x^{1.9}}{x^{2}} = 1000 \lim_{x \to \infty} \frac{1}{x^{0.1}} = 1000 \cdot 0 = 0 \]

この議論を一般化すると次の補題となる:

補題 14.7.2

全ての定数 \(c\) に対して、次の関係が成り立つ:

\[ f = o(g) \ \ \longrightarrow \ \ c \cdot f = o(g) \tag{14.29}\]
全ての定数 \(0 \leq a < b\) に対して、次の関係が成り立つ:

\[ x^{a} = o(x^{b}) \tag{14.30}\]

また、対数は任意の冪乗より遅く大きくなることが示せる:

補題 14.7.3

全ての \(a > 1\) と \(\varepsilon > 0\) に対して \(\log_{a} x = o(x^{\varepsilon})\) が成り立つ。

証明任意の \(y \geq 1\) で \(1/y \leq y\) が成り立つ。両辺を \(1\) から \(z\) まで積分すると、次の不等式を得る:

\[ \ln z \leq \frac{z^{2}}{2} \tag{14.31}\]

ただし \(z \geq 1\) である。任意に \(\varepsilon > \delta > 0\) を取り、不等式 \(\text{(14.31)}\) で \(z = \sqrt{x^{\delta}}\) とすれば次が分かる:

\[ \begin{align*} \frac{\delta \ln x}{2} &\leq \frac{x^{\delta}}{2} \\[10pt] \therefore\ \ln x &\leq \frac{x^{\delta}}{\delta} = o(x^{\varepsilon}) \qquad (\text{補題 }\href{#lemma-14-7-2}{14.7.2} \text{ より}) \tag{14.32} \end{align*} \]

関係 \(\text{(14.32)}\) と \(\text{(14.29)}\) より、

\[ \log_{a} x = \frac{\ln x}{\ln a} = o(x^{\varepsilon}) \]

を得る。 ■

系 14.7.4

\(a, b \in \mathbb{R}\) で \(a > 1\) なら、\(x^{b} = o(a^{x})\) が成り立つ。

補題 14.7.3 と系 14.7.4 は l'Hôpitalロピタルの定理 (l'Hôpital's rule) や \(\log x\) と \(e^{x}\) に対する Maclaurinマクローリン級数 (Maclaurin series) を使っても証明できる。そういった証明は多くの微積分の教科書に載っている。

14.7.2 ビッグオー

「ビッグオー」記法は最も頻繁に利用される漸近記法であり、何らかの関数 (例えばアルゴリズムの実行時間) が大きくなる速さに上界を与える。標準的な定義は定義 14.7.9 であるものの、まずはビッグオー記法の基本的な性質が分かりやすい異なる定義を示す。

定義 14.7.5

二つの関数 \(f, g \colon \mathbb{R} \to \mathbb{R}\) があり、\(g\) が非負だとする。\(f = O(g)\) と表記される二項関係を次のように定める:

\[ f = O(g) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \limsup_{x \to \infty} \frac{|f(x)|}{g(x)} < \infty \]

この記法をビッグオー記法 (big-o notation) と呼ぶ。

この定義は単なる極限 (limit) ではなく上極限 (limit superior) を使っている¹。ただ、極限が存在するとき極限と上極限は一致するので、この定義だとビッグオーの基本的な性質の確認が容易になる。これからの議論で次の補題は証明せずに用いる:

補題 14.7.6

関数 \(f \colon \mathbb{R} \to \mathbb{R}\) に引数が無限に向かうときの極限が存在するなら、次の等式が成り立つ:

\[ \lim_{x \to \infty} f(x) = \limsup_{x \to \infty} f(x) \]

次の補題は定義 14.7.5 から直ちに従う:

補題 14.7.7

\(f = o(g)\) または \(f \sim g\) なら \(f = O(g)\) が成り立つ。

証明定義 14.7.1 と定義 14.4.2 より、\(f = o(g)\) と \(f \sim g\) はそれぞれ \(\lim f/g = 0\) と \(\lim f/g = 1\) を意味する。よって補題 14.7.6 より両方の場合で \(\limsup f/g < \infty\) が分かる。 ■

補題 14.7.7 の逆は正しくないことに注意してほしい。例えば \(2x = O(x)\) は成り立つものの、\(2x \not\sim x\) および \(2x \neq o(x)\) である。

また、次の補題も分かる:

補題 14.7.8

\(f = o(g)\) なら \(g = O(f)\) でない。

証明 \(f = o(g)\) のとき \(\displaystyle \lim_{x \to \infty} f(x) / g(x) = 0\) なので、

\[ \lim_{x \to \infty} \frac{g(x)}{f(x)} = \frac{1}{\lim\limits_{x \to \infty} f(x)/g(x)} = \infty \]

が分かる。よって補題 14.7.6 より \(g \neq O(f)\) である。 ■

定義 14.7.5 で上極限が必要なのは、極限が存在しないケースに対応するためである。例えば、\(f(x) / g(x)\) が \(3\) と \(5\) の間を振動するとき \(\lim_{x \to \infty} f(x) / g(x)\) は存在しないものの、\(\limsup_{x \to \infty} f(x) / g(x) = 5\) は成り立つので \(f = O(g)\) が言える。

ビッグオー記法の上極限を使わない同値な定義を次に示す。他の文献ではこちらの定義が使われることが多い:

定義 14.7.9

二つの関数 \(f, g \colon \mathbb{R} \to \mathbb{R}\) があり、\(g\) が非負だとする。このとき \(f = O(g)\) と表記される二項関係を次のように定める:

\[ \begin{aligned} f=O(g) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ & \text{ある \(c \geq 0\) と \(x_{0}\) が存在して、} \\ & \text{全ての \(x \geq x_{0}\) で \(|f(x)| \leq c g(x)\) が成り立つ} \end{aligned} \]

この定義は複雑な見た目をしているものの、その意味は単純である: \(f(x) = O(g(x))\) は「定数 \(c\) による乗算が自由に可能で、さらに \(x_{0}\) より小さい \(x\) を無視できるとき、\(f(x)\) の絶対値は常に \(g(x)\) 以下である」を意味する。例えば、先ほど考えた \(f(x)/g(x)\) が \(3\) と \(5\) の間を振動するケースでは、定義 14.7.9 を使うなら \(f \leq 5g\) から \(f = O(g)\) が分かる。

命題 14.7.10

\[ 100x^{2} = O(x^{2}) \]

証明全ての \(x \geq 1\) で \(|100x^{2}| \leq 100x^{2}\) なので、定義 14.7.9 で \(c = 100\), \(x_{0} = 1\) とすれば \(100x^{2} = O(x^{2})\) が成り立つ。 ■

命題 14.7.11

\[ x^{2} + 100x + 10 = O(x^{2}) \]

証明次の関係が成り立つ:

\[ \lim_{x \to \infty}\frac{x^{2} + 100x + 10}{x^{2}} = \lim_{x \to \infty} \left( 1 + \frac{100}{x} + \frac{10}{x^{2}} \right) = 1 \]

よって実際には \(x^{2} + 100x + 10 \sim x^{2}\) であり、補題 14.7.7 より \(x^{2} + 100x + 10 = O(x^{2})\) が成り立つ。なお、逆の \(x^{2} = O(x^{2} + 100x + 10)\) も成り立つ。 ■

命題 14.7.11 は任意の多項式に関する命題に一般化できる:

命題 14.7.12

\[ a_{k} x^{k} + a_{k-1}x^{k-1} + \cdots + a_{1} x + a_{0} = O(x^{k}) \]

退屈な証明は省略する。

ビッグオー記法はアルゴリズムの実行時間を表現するとき特に有用となる。例えば、二つの \(n \times n\) 行列を乗じる最も単純なアルゴリズムが最悪の場合に実行する演算の回数は \(n^{3}\) に比例する。この事実は「実行時間が \(O(n^{3})\)」と簡潔に表現できる。漸近記法を使うと、プログラミング言語やマシンに特有の実装詳細を抽象化したアルゴリズムの振る舞いに関する本質的な性質を記述できる。

行列の乗算を \(O(n^{2.55})\) 回の演算で実行するアルゴリズムが存在する²。このアルゴリズムは単純なアルゴリズムより漸近的に高速なので、十分に大きな行列の乗算では必ず高速になる。しかし、漸近的に高速なアルゴリズムが常に正しい選択になるとは限らない。実際、演算回数が \(O(n^{2.55})\) のアルゴリズムは非現実的な大きさの行列を扱わない限り高速にならないので、現実のプログラムで用いられることはまずない。

ただ、\(O(n^{2.55})\) のアルゴリズムが存在する事実は、\(O(n^{3})\) のアルゴリズムを限界まで最適化した実装にも含まれない新しいアイデアの存在を示唆する。現在知られているものより格段に高速な実用的行列乗算プログラムがこの新しいアイデアから生まれる可能性はある。

14.7.3 シータ

実行時間 \(T(n)\) が定数倍を無視してちょうど二次的 (二次関数が上限かつ下限) である事実を表現したい場合がある。これは「\(T(n) = O(n^{2})\) かつ \(n^{2} = O(T(n))\)」と書けば済む。しかし、数学者たちはまたしても専用の記号を考案した。この事実は \(\Theta\) で表現される:

定義 14.7.13

\[ f = \Theta(g) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ f = O(g) \ \operatorname{\text{\footnotesize AND}} \ g = O(f) \]

\(f = \Theta (g)\) を直感的に言い換えれば「\(f\) と \(g\) は定数倍の範囲で等しい」となる。

このシータ記法 (theta notation) を使うと、関数が大きくなる速さに最も寄与する項に注目し、次数の低い項や重要でない項を無視できる。例えば、何らかのアルゴリズムの実行時間 \(T(n)\) が次のように求まったとしよう:

\[ T(n) = 10n^{3} - 20n^{2} + 1 \]

このとき、重要なのは次の単純な式で表される事実である場合が多い:

\[ T(n) = \Theta (n^{3}) \]

このとき「\(T\) は \(n^{3}\) のオーダー (order) である」とか「\(T(n)\) は三次的に大きくなる」などと言う。もう一つ例を示す:

\[ \pi^{2} 3^{x-7} + \frac{(2.7 x^{113} + x^{9} + 86)^{4}}{\sqrt{x}} - 1.08^{3x} = \Theta (3^{x}) \]

アルゴリズムの実行時間が (例えば) \(\Theta (n^{3})\) であるという事実だけでも意味のある情報となる。この情報があれば、\(n\) が十分大きいなら \(n\) が \(2\) 倍になるとき実行時間はおよそ³ \(8\) 倍になると分かる。つまり、シータ記法を使うとアルゴリズムやシステムのスケーラビリティを伝えることができる。当然、スケーラビリティはアルゴリズムやシステムの設計で大きな問題となる。

14.7.4 漸近記法の落とし穴

漸近記法を使って間違った議論をする方法は数多くある。本項では、ビッグオー記法に関する落とし穴をいくつか示す。他の漸近記法にも同じだけの落とし穴が空いていると思った方がいい。

指数の扱い

ビッグオー記法の表現する関係が明らかでない場合がある。例えば、\(4\) は \(2\) の定数倍なので \(4^{x} = O(2^{x})\) だと思うかもしれない。しかし、これは間違っている。\(4^{x}\) は \(2^{x}\) の二乗に等しく、定数倍ではない。

定数の和

全ての定数は \(O(1)\) である。例えば \(17 = O(1)\) が成り立つ。なぜなら、\(f(x) = 17\), \(g(x) = 1\) としたとき、\(c > 0\) と \(x_{0}\) であって全ての \(x \geq x_{0}\) が \(|f(x)| \leq cg(x)\) を満たすものが存在するからである。具体的には、\(c = 17\) および \(x_{0} = 1\) とすれば全ての \(x \geq 1\) で \(|17| \leq 17 \cdot 1\) が成り立つ。この事実を誤用すると、誤った定理を証明できる:

誤った定理 14.7.14

\[ \sum_{i=1}^{n} i = O(n) \]

誤った証明 \(f(n)\) を次のように定める:

\[ f(n) ::= \sum_{i=1}^{n} 1 + 2 + 3 + \cdots + n \]

上述した通り任意の定数 \(i\) は \(O(1)\) なので次の関係が成り立つ:

\[ f(n) = \underbrace{O(1) + O(1) + \cdots + O(1)}_{\text{\(n\) 個}} = O(n) \]

■

しかし当然、正しくは \(\displaystyle \sum_{i=1}^{n} i = n(n+1)/2 \neq O(n)\) である。

この誤りは、\(i = O(1)\) の意味に関する誤解から生まれている。任意の定数 \(i \in \mathbb{N}\) に対して \(i = O(i)\) は正しい。さらに正確に言えば、\(f\) が任意の定数関数なら \(f = O(1)\) である。しかし上記の誤った証明において、\(i\) は定数でない ── その値は \(0\), \(1\), \(\ldots\), \(n\) であり、\(n\) によって変化する。

また、そもそも \(O(1)\) を数値であるかのように足すべきではない。\(O(g)\) という表現が単体で何を意味するかは定義していない: 定義したのは二つの関数 \(f\), \(g\) 間に定義される二項関係であり、それが \(f = O(g)\) と表現されるに過ぎない。

等号の意味

\(f = O(g)\) という記法は現代の数学に深く刻み込まれているので今になって変えることはできないものの、この記法で等号 \(=\) が使われるのは残念なことである。例えば、この記法だと \(f = O(g)\) が \(O(g) = f\) を意味するかのように思える。しかし、もし \(2n = O(n)\) のとき \(O(n) = 2n\) が言えるとしたら、\(n = O(n)\) でもあるので \(n = O(n) = 2n\) と結論できてしまう。こういった間違った議論をしないために、本書では \(O(f) = g\) という表記を使用しない。

関連する話題として、多くの文献では次のような表記が使われる:

\[ \begin{aligned} H_{n} &= \ln n + \gamma + O \left( \frac{1}{n} \right) \\[15pt] n! &= (1 + o(1)) \sqrt{2 n \pi } \left( \frac{n}{e} \right)^{\! n} \end{aligned} \]

これらの表記はそれぞれ次の事実を意味する:

\[ \begin{aligned} H_{n} &= \ln n + \gamma + f(n) \text{ と } f(n) = O \left( \dfrac{1}{n} \right) \text{ を満たす関数 \(f(n)\) が存在する} \\[15pt] n! &= (1 + g(n)) \sqrt{2 n \pi } \left( \frac{n}{e} \right)^{\! n} \text{ と } g(n) = o \left( 1 \right) \text{ を満たす関数 \(g(n)\) が存在する} \\ \end{aligned} \]

こういった記号の濫用は問題ないとされている。あなたも (意味を理解しているなら) 使って構わない。

関数の適用

慣れ親しんだ関数の適用で漸近関係が保存されると考えたくなるかもしれないが、常に保存されるとは限らない。例えば、\(f \sim g\) は一般に \(3^{f} = \Theta(3^{g})\) さえ意味しない。一方で、漸近関係を保存する、ときには強化する関数適用も存在する。次に例を示す:

\[ f = \Theta(g) \ \ \longrightarrow \ \ \ln f \sim \ln g \]

詳しくは問題 14.27 を参照してほしい。

14.7.5 オメガ [スキップ可]

ビッグオー記法が誤って下界を表すのに使われることがある。ビッグオー記法で表せるのは上界だけなので、例えば「実行時間 \(T(n)\) は少なくとも \(O(n^{2})\) だ」という文章は意味をなさない。強いて言うなら、次のように書けば正しい:

\[ n^{2} = O(T(n)) \]

この関係を表現するためのビッグオメガ記法 (big omega notation) が存在する:

定義 14.7.15

二つの関数 \(f, g \colon \mathbb{R} \to \mathbb{R}\) があり、\(f\) が非負だとする。\(f = \Omega (g)\) の意味を次のように定める:

\[ f = \Omega(g) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ g = O(f) \]

例えば \(x^{2} = \Omega(x)\), \(2^{x} = \Omega(x^{2})\), \(x/100 = \Omega(100x + \sqrt{x})\) が成り立つ。また、考えているアルゴリズムの実行時間が入力サイズを \(n\) としたとき \(T(n)\) なら、実行時間が \(n\) に関して少なくとも二次的に増加する事実は次のように表現できる:

\[ T(n) = \Omega (n^{2 }) \]

リトルオー記法に対応するリトルオメガ記法 (little omega notation) も存在する:

定義 14.7.16

二つの関数 \(f, g \colon \mathbb{R} \to \mathbb{R}\) があり、\(f\) が非負だとする。\(f = \omega (g)\) の意味を次のように定める:

\[ f = \omega(g) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ g = o(f) \]

例えば \(x^{1.5} = \omega(x)\) や \(\sqrt{x} = \omega(\ln^{2} x)\) が成り立つ。なお、リトルオメガ記法は他の漸近記法ほどは広く使われていない。

上極限の正確な定義を示す:

\[ \limsup_{x \to \infty} h(x) ::= \lim_{x \to \infty} \operatornamewithlimits{lub}\limits_{y \geq x} h(y) \]

ここで \(\text{lub}\) は上限 (least upper bound, 最小上界) を表す。 ↩︎
実行時間が \(O(n^{2})\) の行列乗算アルゴリズムの存在は理論的に否定されていないものの、誰も見つけられていない。 ↩︎
\(T(n) = \Theta (n^{3})\) は、定数 \(c\), \(d\) (\(0 < c < d\)) が存在して \(T(n)\) が \(cn^{3}\) と \(dn^{3}\) の間にあることを意味する。そのため \(T(2n)\) は \(T(n)\) の \(8d/c\) 倍以下である。この係数が全ての大きな \(n\) で \(8\) に近くなるのは \(T(n) \sim n^{3}\) のときに限られる。 ↩︎