ソート・探索の最悪比較回数

二分探索・マージ（併合）・挿入ソートなどの最悪の比較回数を数え、決定木による下界 $⌈ lo g_{2} n!⌉$ を求められる

前提

対数の定義と性質（数学II 指数関数と対数関数）
順列・円順列・重複順列（数学A 場合の数と確率）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）

説明

比較だけを使うアルゴリズム（探索・併合・整列）が、最悪の場合に何回比較するかを正確に数えられるようになります。代表的な結果は、二分探索が $⌊ lo g_{2} n ⌋ + 1$ 回、長さ $m, n$ の整列済み列の併合が $m + n - 1$ 回、挿入ソートが $\frac{n ( n - 1 )}{2}$ 回です。さらに「どんなに工夫した比較ソートでも最悪 $⌈ lo g_{2} n!⌉$ 回は比較が必要」という下界を、決定木という考え方で求めます。アルゴリズムの効率を比べるときや、これ以上速くできない限界を知りたいときに使います。

なぜそうしてよいのか

【個別のアルゴリズム】二分探索では、整列済みの $n$ 個の中央の要素と目標を比べ、1 回の比較で「等しい・小さい・大きい」がわかるとします。等しくなければ、残る候補は中央より左か右の一方で、多いほうでも $⌊ n /2 ⌋$ 個です。最悪回数を $T (n)$ とすると $T (n) = 1 + T (⌊ n /2 ⌋)$ , $T (0) = 0$ です。 $2^{k} \leq n < 2^{k + 1}$ なら $2^{k - 1} \leq ⌊ n /2 ⌋ < 2^{k}$ となり、半分にするたびに $k$ が 1 ずつ減るので、 $T (n) = k + 1 = ⌊ lo g_{2} n ⌋ + 1$ です。併合では、1 回比べるごとに小さいほうを 1 個出力します。片方の列が空になれば残りは比較なしで並べられ、最後の 1 個は必ず比較なしで出るので、比較は高々 $m + n - 1$ 回です。両方の列の最後の要素が全体の大きいほうから 2 つを占めるときなど、この回数になる入力があります。挿入ソートでは、 $i$ 番目（ $i = 2, \dots, n$ ）の要素を、整列済みの $i - 1$ 個に右から比べて差し込みます。入力が逆順なら毎回 $i - 1$ 回比べるので、合計は $1 + 2 + \dots + (n - 1) = \frac{n ( n - 1 )}{2}$ 回です。

【下界：決定木】比較ソートの動きを、樹形図として描きます。各分かれ目が 1 回の比較（ $a_{i} < a_{j}$ か否か）で、2 本に枝分かれします。末端（葉）では並べ替え方が 1 つに決まります。異なる $n$ 個の数の並び方は $n!$ 通りあります。異なる並び方が同じ葉に着くと同じ並べ替えが行われてしまい、両方を正しく整列できません。したがって葉は $n!$ 個以上必要です。一方、最悪比較回数（根から葉までの最長の道の比較数）が $h$ なら、積の法則により葉は高々 $2^{h}$ 個です。

よって $2^{h} \geq n!$ 、すなわち $h \geq lo g_{2} n!$ です。 $h$ は整数なので $h \geq ⌈ lo g_{2} n!⌉$ となります（ $⌈ x ⌉$ は $x$ 以上の最小の整数）。これは「どの比較ソートも、最悪の場合これ以上の回数は比較する」という限界です。

手順

1 回の比較で何がわかるかを確認する（整列は「 $<$ か $>$ 」の 2 分岐、二分探索は「 $=, <, >$ 」の 3 通り）。
二分探索の最悪回数： $2^{k} \leq n < 2^{k + 1}$ となる整数 $k$ を見つけ、 $⌊ lo g_{2} n ⌋ + 1 = k + 1$ 回とする。
併合の最悪回数：長さ $m, n$ （ともに 1 以上）の整列済み列なら $m + n - 1$ 回。
挿入ソートの最悪回数： $\sum_{i = 2}^{n} (i - 1) = \frac{n ( n - 1 )}{2}$ 回（入力が逆順のとき）。
比較ソートの下界： $n!$ を計算し、 $2^{h} \geq n!$ となる最小の整数 $h$ を求める。この $h$ が $⌈ lo g_{2} n!⌉$ である。

例題

相異なる 5 個の数を、2 数の大小比較だけを用いて整列する。どのような比較ソートでも最悪の場合に必要な比較回数の、決定木による下界 $⌈ lo g_{2} 5!⌉$ を求めよ。

例題の解答

手順1：比較は「 $<$ か $>$ 」の 2 分岐なので、最悪 $h$ 回の比較で区別できる並び方は高々 $2^{h}$ 通りである。
手順5：区別すべき並び方は $5! = 120$ 通りなので、 $2^{h} \geq 120$ となる最小の整数 $h$ を探す。 $2^{6} = 64 < 120$ 、 $2^{7} = 128 \geq 120$ である。よって $6 < lo g_{2} 120 \leq 7$ となり、 $⌈ lo g_{2} 120 ⌉ = 7$ である。したがって、どの比較ソートも最悪の場合 7 回以上は比較する。

答え: $7$

よくある誤り

$⌈ lo g_{2} n!⌉$ を $n lo g_{2} n$ や $⌈ lo g_{2} n ⌉$ と取り違える誤り。 $n = 5$ では $5 lo g_{2} 5 \approx 11.6$ 、 $⌈ lo g_{2} 5 ⌉ = 3$ となるが、正しくは $⌈ lo g_{2} 120 ⌉ = 7$ である。
二分探索の最悪回数を $⌈ lo g_{2} n ⌉$ としてしまう誤り。 $n = 8$ では 3 になってしまうが、等しいかどうかを確かめる比較も数えると、正しくは $⌊ lo g_{2} 8 ⌋ + 1 = 4$ 回である。
併合の最悪回数を $m + n$ 回とする誤り。最後の 1 個は比較なしで出力できるので、正しくは $m + n - 1$ 回である（例： $m = n = 3$ なら 5 回）。
下界 $⌈ lo g_{2} n!⌉$ を、必ず達成できる最小回数だと思い込む誤り。これは「これより少なくはできない」という保証にすぎない。たとえば $n = 12$ では $⌈ lo g_{2} 12!⌉ = 29$ だが、実際に必要な最小の最悪回数は 30 である。

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

入口の問題

この技能を使う問題

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

ソートの平均比較回数と転倒数（大学数学アルゴリズムと計算量）