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

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

難易度 2教科書の演習問題レベル証明問題大学数学アルゴリズムと計算量

正の整数 $n$ に対して
$S (n) = k = 1 \sum n k lo g k$
とおく（ $lo g$ は自然対数）。ここで、正の整数上で定義された非負の値をとる関数 $f, g$ について $f (n) = Θ (g (n))$ とは、正の定数 $c_{1}, c_{2}$ と正の整数 $n_{0}$ が存在して、 $n \geq n_{0}$ を満たすすべての整数 $n$ に対して $c_{1} g (n) \leq f (n) \leq c_{2} g (n)$ が成り立つことと定める。

このとき、 $S (n) = Θ (n^{2} lo g n)$ であることを証明せよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

上からの評価と下からの評価に分けて、定義の定数 $c_{1}, c_{2}, n_{0}$ を具体的に見つけましょう。

ヒント 2

上からは、各項を最大の項 $n lo g n$ で抑えます。下からは、 $k \geq n /2$ の項だけを残し、それぞれを $\frac{n}{2} lo g \frac{n}{2}$ で下から抑えます。

ヒント 3

下からの評価で $S (n) \geq \frac{n ^{2}}{4} lo g \frac{n}{2}$ が得られます。あとは $n$ が十分大きいとき $lo g \frac{n}{2}$ が $lo g n$ の定数倍以上になることを、 $lo g 2$ と $lo g n$ を比べて示しましょう。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$x lo g x$ が $x \geq 1$ で単調非減少かつ非負であることを確認し、各項を $n lo g n$ 以下と評価して $S (n) \leq n^{2} lo g n$ を導いている（3 点）
項が非負であることを根拠に、 $k \geq ⌈ n /2 ⌉$ の項だけを残して和を下から評価している（2 点）
残した項の個数が $n /2$ 以上であることと、各項が $\frac{n}{2} lo g \frac{n}{2}$ 以上であることを示し、 $S (n) \geq \frac{n ^{2}}{4} lo g \frac{n}{2}$ を得ている（2 点）
$n \geq 4$ などの条件のもとで $lo g \frac{n}{2} \geq \frac{1}{2} lo g n$ を示し、 $S (n) \geq c_{1} n^{2} lo g n$ の形にしている（2 点）
定数 $c_{1}, c_{2}, n_{0}$ を明示して、定義どおりに $S (n) = Θ (n^{2} lo g n)$ と結論している（1 点）

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

模範解答を読む

定義に従い、正の定数 $c_{1}, c_{2}$ と正の整数 $n_{0}$ を具体的に見つけ、 $n \geq n_{0}$ のとき $c_{1} n^{2} lo g n \leq S (n) \leq c_{2} n^{2} lo g n$ が成り立つことを示す。以下、 $c_{2} = 1$ , $c_{1} = \frac{1}{8}$ , $n_{0} = 4$ がとれることを示す。

上からの評価. 関数 $x \mapsto x lo g x$ は $x \geq 1$ で $x \geq 1$ , $lo g x \geq 0$ がともに単調非減少で非負なので、その積も $x \geq 1$ で単調非減少である。よって $1 \leq k \leq n$ のとき $k lo g k \leq n lo g n$ が成り立つ。これを $k = 1, 2, \dots, n$ の $n$ 個について足すと
$S (n) = k = 1 \sum n k lo g k \leq n \cdot n lo g n = n^{2} lo g n$
となる。これはすべての正の整数 $n$ で成り立つ。

下からの評価. $n \geq 4$ とし、 $m = ⌈ n /2 ⌉$ とおく。各項 $k lo g k$ は $k \geq 1$ で $0$ 以上なので、 $k < m$ の項を捨てても和は増えない：
$S (n) \geq k = m \sum n k lo g k .$
右辺の項数は $n - m + 1 = n - ⌈ n /2 ⌉ + 1 = ⌊ n /2 ⌋ + 1$ であり、 $⌊ n /2 ⌋ > n /2 - 1$ より項数は $\frac{n}{2}$ より大きい。また $m \leq k \leq n$ のとき $k \geq m \geq \frac{n}{2} \geq 2$ なので、上で述べた単調性から $k lo g k \geq \frac{n}{2} lo g \frac{n}{2}$ であり、 $\frac{n}{2} \geq 2$ よりこの値は正である。したがって
$S (n) \geq \frac{n}{2} \cdot \frac{n}{2} lo g \frac{n}{2} = \frac{n ^{2}}{4} (lo g n - lo g 2) .$
ここで $n \geq 4$ のとき $lo g n \geq lo g 4 = 2 lo g 2$ 、すなわち $lo g 2 \leq \frac{1}{2} lo g n$ である。よって $lo g n - lo g 2 \geq \frac{1}{2} lo g n$ となり、
$S (n) \geq \frac{n ^{2}}{4} \cdot \frac{1}{2} lo g n = \frac{1}{8} n^{2} lo g n$
が $n \geq 4$ で成り立つ。

結論. 以上より、 $c_{1} = \frac{1}{8}$ , $c_{2} = 1$ , $n_{0} = 4$ とすると、 $n \geq n_{0}$ のすべての整数 $n$ で
$\frac{1}{8} n^{2} lo g n \leq S (n) \leq n^{2} lo g n$
が成り立つ。 $S (n)$ と $n^{2} lo g n$ はともに非負なので、定義により $S (n) = Θ (n^{2} lo g n)$ である。 $■$

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

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題