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

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

難易度 3期末試験の応用レベル大学数学アルゴリズムと計算量

$n$ を $2$ 以上の整数とし、 $n$ の関数として次の $8$ 個の計算時間を考える（ $lo g$ は自然対数、 $lo g_{2}$ は底 $2$ の対数）。
$f_{1} (n) = (lo g_{2} n)^{l o g_{2} n}, f_{2} (n) = n^{3}, f_{3} (n) = 2^{2 l o g_{2} n}, f_{4} (n) = (lo g_{2} n)^{5},$
$f_{5} (n) = (n 2 n), f_{6} (n) = k = 1 \sum n k^{2} lo g k, f_{7} (n) = 3^{n}, f_{8} (n) = lo g_{2} (n!)$
正の値をとる関数 $f, g$ について、 $n \to \infty lim \frac{f ( n )}{g ( n )} = 0$ が成り立つことを $f = o (g)$ と書く。
$1$ から $8$ までの番号を並べかえた組 $(i_{1}, i_{2}, \dots, i_{8})$ で
$f_{i_{1}} = o (f_{i_{2}}), f_{i_{2}} = o (f_{i_{3}}), \dots, f_{i_{7}} = o (f_{i_{8}})$
がすべて成り立つものがただ $1$ つ存在する。この組 $(i_{1}, i_{2}, \dots, i_{8})$ を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

すべての関数を $2^{(何か)}$ の形に直したり、 $Θ$ で簡単な形に評価したりして、「多項式より遅い」「多項式」「多項式より速いが指数関数より遅い」「指数関数」のグループに分けよう。

ヒント 2

$(lo g_{2} n)^{l o g_{2} n} = n^{l o g_{2} l o g_{2} n}$ 、 $2^{2 l o g_{2} n}$ は対数をとると $2 lo g_{2} n$ 、 $lo g_{2} (n!) = Θ (n lo g n)$ 、 $\frac{4 ^{n}}{2 n + 1} \leq (n 2 n) \leq 4^{n}$ を使う。

ヒント 3

$\sum k^{2} lo g k = Θ (n^{3} lo g n)$ なので $n^{3}$ より速い。最も遅いのは $(lo g_{2} n)^{5}$ 、その次が $2^{2 l o g_{2} n}$ である。残りを $n lo g n$ , $n^{3}$ , $n^{3} lo g n$ , $n^{l o g_{2} l o g_{2} n}$ , $3^{n}$ , $4^{n} / (多項式)$ の順に比べよう。

答えと解説

答えを見る

(4, 3, 8, 2, 6, 1, 7, 5)

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

解説を読む

$L = lo g_{2} n$ とおく。 $n \to \infty$ のとき $L \to \infty$ である。各関数の大きさを調べ、隣どうしを比較する。

各関数の評価
- $f_{1} = (lo g_{2} n)^{l o g_{2} n} = 2^{L l o g_{2} L} = n^{l o g_{2} L}$ 。指数 $lo g_{2} L$ が $\infty$ に発散するので、どんな多項式よりも速く増える。
- $f_{6}$ ： $k \leq n$ なので $f_{6} \leq n \cdot n^{2} lo g n = n^{3} lo g n$ 。また $k = ⌈ n /2 ⌉, \dots, n$ の少なくとも $n /2$ 個の項はどれも $(n /2)^{2} lo g (n /2)$ 以上なので $f_{6} \geq \frac{n}{2} \cdot \frac{n ^{2}}{4} lo g \frac{n}{2} = \frac{n ^{3}}{8} lo g \frac{n}{2}$ 。よって $f_{6} = Θ (n^{3} lo g n)$ 。
- $f_{8} = lo g_{2} (n!)$ ： $n! \leq n^{n}$ より $f_{8} \leq n L$ 。また $n! \geq (n /2)^{n /2}$ （大きいほうの半分の因数がそれぞれ $n /2$ 以上）より $f_{8} \geq \frac{n}{2} lo g_{2} \frac{n}{2}$ 。よって $f_{8} = Θ (n lo g n)$ 。
- $f_{5} = (n 2 n)$ ：二項係数 $(0 2 n), \dots, (2 n 2 n)$ の $2 n + 1$ 個の和は $2^{2 n} = 4^{n}$ で、 $(n 2 n)$ はその最大のものなので $\frac{4 ^{n}}{2 n + 1} \leq f_{5} \leq 4^{n}$ 。

隣どうしの比較
1. $f_{4} = o (f_{3})$ ： $lo g_{2} \frac{f _{4}}{f _{3}} = 5 lo g_{2} L - 2 L \to - \infty$ （ $lo g L$ は $L$ より遅く増える）。よって比は $0$ に収束する。
2. $f_{3} = o (f_{8})$ ： $n \geq 4$ で $f_{8} \geq \frac{n}{2} lo g_{2} \frac{n}{2} \geq \frac{n}{2}$ なので $\frac{f _{3}}{f _{8}} \leq \frac{2 \cdot 2 ^{2 L}}{2 ^{L}} = 2^{1 + 2 L - L} \to 0$ 。
3. $f_{8} = o (f_{2})$ ： $\frac{f _{8}}{f _{2}} \leq \frac{n L}{n ^{3}} = \frac{lo g _{2} n}{n ^{2}} \to 0$ 。
4. $f_{2} = o (f_{6})$ ： $\frac{f _{6}}{f _{2}} \geq \frac{1}{8} lo g \frac{n}{2} \to \infty$ なので $\frac{f _{2}}{f _{6}} \to 0$ 。
5. $f_{6} = o (f_{1})$ ： $n \geq 3$ で $lo g n \leq n$ より $f_{6} \leq n^{4}$ 。 $\frac{f _{6}}{f _{1}} \leq n^{4 - l o g_{2} L}$ で、 $L > 2^{5}$ となる $n$ では指数が $- 1$ 以下なので $\leq \frac{1}{n} \to 0$ 。
6. $f_{1} = o (f_{7})$ ： $lo g_{2} \frac{f _{1}}{f _{7}} = L lo g_{2} L - n lo g_{2} 3$ 。 $L lo g_{2} L \leq L^{2} = (lo g_{2} n)^{2}$ で、 $\frac{( lo g _{2} n ) ^{2}}{n} \to 0$ だから、これは $- \infty$ に発散する。
7. $f_{7} = o (f_{5})$ ： $\frac{f _{7}}{f _{5}} \leq \frac{( 2 n + 1 ) 3 ^{n}}{4 ^{n}} = (2 n + 1) (\frac{3}{4})^{n} \to 0$ 。

以上より $f_{4} = o (f_{3}), f_{3} = o (f_{8}), f_{8} = o (f_{2}), f_{2} = o (f_{6}), f_{6} = o (f_{1}), f_{1} = o (f_{7}), f_{7} = o (f_{5})$ が成り立つ。 $o$ の関係は推移的で、 $f = o (g)$ なら $g = o (f)$ ではないので、条件を満たす並べ方はこれだけである。

答え： $(4, 3, 8, 2, 6, 1, 7, 5)$

別解

$L = lo g_{2} n$ とおき、各関数の増加の速さを調べる。

$f_{4} = L^{5} = exp (5 ln L)$ 、 $f_{3} = 2^{2 L} = exp (c L)$ （ $c = 2 ln 2$ ）。 $L$ は $ln L$ より速く増えるので $f_{4} = o (f_{3})$ 。
$f_{3} = exp (O (lo g n))$ は $n$ のどんな正のべきよりも遅い。よって $f_{3} = o (f_{8})$ 。
$f_{8} = lo g_{2} (n!) \sim n lo g_{2} n$ なので $f_{8} = o (n^{3}) = o (f_{2})$ 。
$f_{6} = \sum_{k = 1}^{n} k^{2} lo g k \sim \frac{1}{3} n^{3} lo g n$ なので $f_{2} = o (f_{6})$ 。
$f_{1} = L^{L} = 2^{L l o g_{2} L} = n^{l o g_{2} l o g_{2} n}$ は、どんな多項式よりも速く増える。よって $f_{6} = o (f_{1})$ 。
$f_{1} = n^{l o g_{2} l o g_{2} n} = exp (lo g n \cdot lo g_{2} lo g_{2} n)$ は指数関数 $e^{an}$ （ $a > 0$ ）より遅い。よって $f_{1} = o (3^{n})$ 。
$f_{5} = (n 2 n) \sim 4^{n} / π n$ なので、 $f_{7} / f_{5} \sim π n (3/4)^{n} \to 0$ 。よって $f_{7} = o (f_{5})$ 。

以上より、小さい順に $f_{4}, f_{3}, f_{8}, f_{2}, f_{6}, f_{1}, f_{7}, f_{5}$ となる。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題