この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

アルゴリズムと計算量の問題

難易度 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$ を表す。

この問題で使うもの

計算量のオーダーの比較（説明と入口の問題）

この問題を解けるようになるまで（19 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

「計算量のオーダーの比較」を使います。4 つの関数はどれも正なので、自然対数をとって指数の部分の大きさを比べましょう。

ヒント 2

$lo g g (n) - lo g f (n) \to \infty$ なら $f = o (g)$ です。対数をとると、 $100 lo g n$ , $n lo g 2$ , $(lo g n)^{2}$ , $5 lo g (lo g n)$ になります。

ヒント 3

$lo g n$ を $t$ とおくと、 $5 lo g t$ , $100 t$ , $t^{2}$ は多項式・対数の比較で順序がわかります。残りは $(lo g n)^{2}$ と $n lo g 2$ のどちらが速く増えるかを、 $\frac{( lo g n ) ^{2}}{n}$ の極限で調べましょう。

答えと解説

答えを見る

(4, 1, 3, 2)

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

どの関数も正なので、自然対数をとって比べます。

手順 1：対数をとる
$lo g f_{1} (n) = 100 lo g n, lo g f_{2} (n) = n lo g 2, lo g f_{3} (n) = (lo g n)^{2}, lo g f_{4} (n) = 5 lo g (lo g n)$

手順 2：比べ方の原理
$lo g g (n) - lo g f (n) \to \infty$ ならば
$\frac{f ( n )}{g ( n )} = e^{l o g f (n) - l o g g (n)} \to 0$
なので $f = o (g)$ です。そこで、対数の差が $+ \infty$ に発散するかを調べます。

手順 3：隣どうしを比べる
- $f_{4}$ と $f_{1}$ ： $t = lo g n \to \infty$ とおくと、 $lo g f_{1} - lo g f_{4} = 100 t - 5 lo g t = t (100 - \frac{5 lo g t}{t})$ 。 $\frac{lo g t}{t} \to 0$ なので、これは $+ \infty$ に発散します。よって $f_{4} = o (f_{1})$ 。
- $f_{1}$ と $f_{3}$ ： $lo g f_{3} - lo g f_{1} = (lo g n)^{2} - 100 lo g n = lo g n (lo g n - 100) \to \infty$ 。よって $f_{1} = o (f_{3})$ 。
- $f_{3}$ と $f_{2}$ ： $lo g f_{2} - lo g f_{3} = n (lo g 2 - \frac{( lo g n ) ^{2}}{n})$ 。 $s = lo g n$ とおくと $\frac{( lo g n ) ^{2}}{n} = \frac{s ^{2}}{e ^{s /2}} \to 0$ （指数関数は多項式より速く増える）なので、括弧内は $lo g 2 > 0$ に収束し、全体は $+ \infty$ に発散します。よって $f_{3} = o (f_{2})$ 。

手順 4：並べる
以上より
$f_{4} = o (f_{1}), f_{1} = o (f_{3}), f_{3} = o (f_{2})$
なので、 $(a, b, c, d) = (4, 1, 3, 2)$ です。

別解

各関数の自然対数を比べる。log f1 = 100 log n、log f2 = sqrt(n) log 2、log f3 = (log n)^2、log f4 = 5 log log n。n→∞ で、log log n = o(log n)、log n = o((log n)^2)、(log n)^2 = o(sqrt(n)) なので log f4 < log f1 < log f3 < log f2 の順に増加が速い。さらに、log f_i - log f_j → -∞ となるので f_i/f_j → 0 であり、o の関係が成り立つ。したがって f4 = o(f1)、f1 = o(f3)、f3 = o(f2)。検算: n=e^100 のとき log f1=10000, log f3=10000 で並ぶが、それ以降は f3 が上回る。f2 は sqrt(n) が極めて大きく最大。

アルゴリズムと計算量の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題