計算量のオーダーの比較

対数をとって指数の大きさを比べたり極限 $lim_{n \to \infty} f (n) / g (n)$ を調べたりして、 $n^{3}$ , $2^{n}$ , $(lo g n)^{l o g n}$ などの関数の増え方を $f = o (g)$ の関係で並べられる

前提

関数の極限（数学III 極限）
対数の定義と性質（数学II 指数関数と対数関数）

この技能までの道筋（18 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

四則の混じった計算の順序（算数計算と数のきまり）
等間隔にならんだ数の和（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）

説明

アルゴリズムの実行時間などを表す関数について、 $n \to \infty$ でどちらがどれだけ速く増えるかを判定し、増え方の遅い順に並べられるようになります。正の値をとる関数 $f, g$ について、 $lim_{n \to \infty} f (n) / g (n) = 0$ のとき $f = o (g)$ と書き、「 $f$ は $g$ より真に遅く増える」と読みます。 $n^{3}$ , $2^{n}$ , $(lo g n)^{l o g n}$ のように指数の部分に $n$ を含む関数は見た目では比べにくいので、対数をとって指数どうしを比べます。

なぜそうしてよいのか

十分大きい $n$ で $f (n) > 0$ , $g (n) > 0$ とします。 $\frac{f ( n )}{g ( n )} = e^{l o g f (n) - l o g g (n)}$ と書けて、 $e^{x}$ は増加関数で、 $x \to - \infty$ のとき $e^{x} \to 0$ です。したがって $lo g f (n) - lo g g (n) \to - \infty$ ならば $f (n) / g (n) \to 0$ 、つまり $f = o (g)$ です。逆に $f / g \to 0$ なら $lo g (f / g) \to - \infty$ なので、この 2 つは同じことです。対数をとると $a^{b}$ は $b lo g a$ という積になり、指数の中の $n$ が表に出てくるので比べやすくなります。注意したいのは、見るべきものが対数の『差』だという点です。対数の『比』を見ても判定できません。

差の極限を調べるときの基本の道具は「 $a > 0$ ならば $lim_{x \to \infty} \frac{l o g x}{x ^{a}} = 0$ 」です。これは次のように示せます。 $y > 0$ のとき $e^{y} \geq 1 + y > y$ なので $lo g y < y$ です。 $y = x^{a /2}$ とおくと $\frac{a}{2} lo g x < x^{a /2}$ となり、 $x > 1$ では $0 < \frac{l o g x}{x ^{a}} < \frac{2}{a} x^{- a /2} \to 0$ です。よって、はさみうちにより極限は $0$ です。両辺を $p$ 乗すれば、任意の $p > 0$ について $(lo g x)^{p} = o (x^{a})$ も得られます。

また、 $f = o (g)$ かつ $g = o (h)$ ならば $\frac{f}{h} = \frac{f}{g} \cdot \frac{g}{h} \to 0 \cdot 0 = 0$ なので $f = o (h)$ です。このように $o$ の関係は推移的なので、隣り合う 2 つずつを比べれば全体を並べられます。

手順

各関数の対数 $L_{f} (n) = lo g f (n)$ を計算し、積の形に整理する（例： $lo g 2^{n} = n lo g 2$ 、 $lo g (lo g n)^{l o g n} = lo g n \cdot lo g lo g n$ ）。
2 つずつ差 $L_{f} (n) - L_{g} (n)$ をつくり、いちばん速く増える因子でくくる。
くくった残りの極限を、基本事実 $\frac{( l o g n ) ^{p}}{n ^{a}} \to 0 (a, p > 0)$ とはさみうちで求める。
差が $- \infty$ に発散すれば $f = o (g)$ 、 $+ \infty$ に発散すれば $g = o (f)$ と判定する。差が有界にとどまるなら、どちらも $o$ ではない。
推移性（ $f = o (g)$ , $g = o (h) \Rightarrow f = o (h)$ ）を使って、全体を増え方の遅い順に並べる。

例題

$f_{1} (n) = n^{3}$ , $f_{2} (n) = 2^{n}$ , $f_{3} (n) = (lo g n)^{l o g n}$ （ $n \geq 3$ ）とする。 $f_{a} = o (f_{b})$ かつ $f_{b} = o (f_{c})$ となる $1, 2, 3$ の並べ方 $(a, b, c)$ を求めよ。

例題の解答

手順1：対数をとる。 $n \geq 3$ では $lo g n > 1$ なので、どの関数も正の値をとる。 $L_{1} = 3 lo g n$ , $L_{2} = n lo g 2$ , $L_{3} = lo g n \cdot lo g (lo g n)$ である。

手順2〜4（ $f_{1}$ と $f_{3}$ ）：差を $lo g n$ でくくると $L_{1} - L_{3} = lo g n (3 - lo g lo g n)$ となる。 $n \to \infty$ で $lo g n \to \infty$ 、 $lo g lo g n \to \infty$ なので、この差は $- \infty$ に発散する。よって $f_{1} = o (f_{3})$ 。

手順2〜4（ $f_{3}$ と $f_{2}$ ）：差を $n$ でくくると $L_{3} - L_{2} = n (\frac{l o g n \cdot l o g l o g n}{n} - lo g 2)$ となる。 $lo g y < y$ より $0 < lo g lo g n < lo g n$ なので、 $0 < \frac{l o g n \cdot l o g l o g n}{n} < \frac{( l o g n ) ^{2}}{n} = (\frac{l o g n}{n ^{1/4}})^{2} \to 0$ が成り立つ。はさみうちにより、かっこの中は $- lo g 2 < 0$ に収束する。 $n \to \infty$ だから差は $- \infty$ に発散し、 $f_{3} = o (f_{2})$ 。

手順5：推移性から $f_{1} = o (f_{3})$ , $f_{3} = o (f_{2})$ となり、遅い順に $f_{1}, f_{3}, f_{2}$ と並ぶ。したがって $(a, b, c) = (1, 3, 2)$ 。

答え: $(1, 3, 2)$

よくある誤り

対数の比 $\frac{l o g f}{l o g g}$ が $0$ でないからといって、同じ増え方だとしてしまう誤り。例えば $\frac{l o g n}{l o g n ^{2}} = \frac{1}{2}$ だが、 $\frac{n}{n ^{2}} \to 0$ なので $n = o (n^{2})$ である。正しくは、対数の差 $lo g f - lo g g$ が $- \infty$ に発散するかどうかを見る。
指数の中の定数倍を無視して $2^{2 n}$ と $2^{n}$ を同じ増え方としてしまう誤り。正しくは $\frac{2 ^{2 n}}{2 ^{n}} = 2^{n} \to \infty$ なので $2^{n} = o (2^{2 n})$ である。対数の差は $n lo g 2 \to \infty$ で、有界ではない。
$lo g n$ はゆっくり増えるので、 $(lo g n)^{l o g n}$ も多項式程度だとしてしまう誤り。正しくは $lo g (lo g n)^{l o g n} = lo g n \cdot lo g lo g n$ であり、どんな定数 $k$ に対しても $k lo g n$ との差は $lo g n (lo g lo g n - k) \to \infty$ となる。つまり $n^{k} = o ((lo g n)^{l o g n})$ である。
差が $- \infty$ に発散することを示さずに、片方の項が大きくなるという印象だけで判定してしまう誤り。例えば $L_{3} - L_{2}$ では $\frac{l o g n l o g l o g n}{n} \to 0$ をはさみうちで示して、初めてかっこの中が負の定数 $- lo g 2$ に収束すると言える。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（教科書の例題レベル）
$n$ を $3$ 以上の整数とし、 $n$ の関数として次の $4$ つの計算時間を考える（ $lo g$ は自然対数）。
$f_{1} (n) = n^{100}, f_{2} (n) = 2^{n}, f_{3} (n) = n^{l o g n}, f_{4} (n) = (lo g n)^{5}$
これらは、ある並べ方 $f_{a}, f_{b}, f_{c}, f_{d}$ について
$f_{a} = o (f_{b}), f_{b} = o (f_{c}), f_{c} = o (f_{d}) (n \to \infty)$
を満たす。添字の組 $(a, b, c, d)$ を求めよ。ここで $f = o (g)$ は $n \to \infty lim \frac{f ( n )}{g ( n )} = 0$ を表す。

この技能を使う問題

この技能の次に学べること

マスター定理（大学数学アルゴリズムと計算量）
多項式時間多対一帰着の性質（大学院数学計算理論・ラムダ計算）