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

難易度 4大学院入試の標準レベル大学数学アルゴリズムと計算量

互いに異なる $8$ 個の数を並べた配列を、次のマージソートで昇順に並べかえる。

長さ $1$ の配列はそのまま返す。
長さ $2 k$ （ $k$ は正の整数）の配列は、前半 $k$ 個と後半 $k$ 個に分け、それぞれを再帰的にこのマージソートで並べかえたあと、次の「マージ」で $1$ つの昇順の列にまとめる。
マージ: 昇順に並んだ 2 つの列の先頭どうしを $1$ 回比較し、小さい方を取り出して出力の末尾に加える。これを一方の列が空になるまで繰り返し、空になったら、もう一方の列に残っている数を比較せずにそのまま出力の末尾に加える。

入力の $8$ 個の数の並び方は $8!$ 通りすべてが等確率で現れるものとする。このとき、ソート全体で行われる数どうしの比較回数の期待値を求めよ。

この問題で使うもの

ソートの平均比較回数と転倒数（説明と入口の問題）
指示変数と期待値の線形性（説明と入口の問題）
組合せ（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

マージソート全体の比較回数は、各段のマージの比較回数の和である。期待値の線形性を使って、長さ $1 + 1$ 、 $2 + 2$ 、 $4 + 4$ のマージごとに期待値を求めよう。

ヒント 2

一様ランダムな入力では、マージする 2 列の数が小さい順にどう入り混じるか（前半を $A$ 、後半を $B$ とした列）は $(k 2 k)$ 通りが等確率。比較回数は（合計個数） $-$ （最後の同じ文字の連の長さ）になる。

ヒント 3

$A$ が $m$ 個、 $B$ が $n$ 個のとき、末尾の $A$ の連の長さの期待値は $\frac{m}{n + 1}$ 。長さ $k$ どうしのマージの比較回数の期待値は $2 k - \frac{2 k}{k + 1}$ となる。

答えと解説

答えを見る

\frac{236}{15}

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

解説を読む

再帰の構造. 長さ $8$ の配列は長さ $4$ の 2 つに、それぞれの長さ $4$ は長さ $2$ の 2 つに、長さ $2$ は長さ $1$ の 2 つに分かれる。したがって行われるマージは
- 長さ $1$ と $1$ のマージ： $4$ 回
- 長さ $2$ と $2$ のマージ： $2$ 回
- 長さ $4$ と $4$ のマージ： $1$ 回

であり、比較回数の期待値はそれぞれのマージの比較回数の期待値の和（期待値の線形性）になる。

各マージに入る列の並び方. 入力が一様ランダムな順列なので、ある長さ $2 k$ の部分配列について、その $2 k$ 個の数を小さい順に並べたとき「前半 $k$ 個に属する数」がどの順位を占めるかは、 $(k 2 k)$ 通りすべてが等確率である。マージの比較回数はこの順位の並び（前半を $A$ 、後半を $B$ と書いた $A$ $k$ 個・ $B$ $k$ 個の列）だけで決まる。

長さ $k$ と $k$ のマージの比較回数. 合計 $2 k$ 個を出力するが、一方の列が空になったあとに残りをそのまま加える分は比較しない。 $A / B$ の列の末尾にある同じ文字の連なり（最後の連）の長さを $L$ とすると、その $L$ 個は比較なしで出力されるので、比較回数は $2 k - L$ である。

$L$ の期待値を求める。 $A$ の連で終わる場合の連の長さを $L_{A}$ （ $B$ で終わるなら $0$ ）とし、 $L_{B}$ も同様とすると $L = L_{A} + L_{B}$ 。 $L_{A} \geq j$ となるのは末尾 $j$ 文字がすべて $A$ のときで、その確率は
$P (L_{A} \geq j) = \frac{( k - j 2 k - j )}{( k 2 k )} = \frac{k ( k - 1 ) \dots ( k - j + 1 )}{2 k ( 2 k - 1 ) \dots ( 2 k - j + 1 )} (1 \leq j \leq k) .$
これを $j = 1, \dots, k$ について足すと $E [L_{A}] = \frac{k}{k + 1}$ となる（ $A$ の個数 $m$ 、 $B$ の個数 $n$ のとき、末尾の $A$ の連の長さの期待値は $\frac{m}{n + 1}$ ：各 $A$ が「すべての $B$ より後ろ」にある確率が $\frac{1}{n + 1}$ だから）。よって
$E [比較回数] = 2 k - \frac{2 k}{k + 1} .$

$k = 1$ ： $2 - 1 = 1$ （実際、長さ $1$ どうしは必ず $1$ 回）
$k = 2$ ： $4 - \frac{4}{3} = \frac{8}{3}$
$k = 4$ ： $8 - \frac{8}{5} = \frac{32}{5}$

検算（ $k = 2$ ）. $AABB, ABAB, ABBA, BAAB, BABA, BBAA$ の比較回数はそれぞれ $2, 3, 3, 3, 3, 2$ で、平均は $\frac{16}{6} = \frac{8}{3}$ 。

合計.
$4 \cdot 1 + 2 \cdot \frac{8}{3} + \frac{32}{5} = 4 + \frac{16}{3} + \frac{32}{5} = \frac{60 + 80 + 96}{15} = \frac{236}{15} .$

別解

入力が一様ランダムな順列なら、各マージに入る 2 つの列は、それぞれ互いに独立に一様ランダムな相対順序をもち、2 列の要素の混ざり方（どの位置が前半由来か）は、 $(k 2 k)$ 通りが等確率になる。

長さ $k$ と $k$ の昇順列のマージの比較回数 $C_{k}$ を求める。一方の列が空になった時点で、もう一方に残っている要素数を $R$ とすると、比較回数は $C_{k} = 2 k - R$ （比較 1 回ごとに 1 個出力され、残りは比較なしで出力されるため）。

$R$ の期待値: 出力列の末尾に連続して並ぶ「同じ列由来の要素」の個数が $R$ 。全体の最大値が前半由来のとき、末尾の連続する前半由来の個数 $r$ について、末尾から $r$ 個が前半由来で、その直前が後半由来（または全部が前半由来）。
$E [R] = \sum_{j \geq 1} P (R \geq j)$ 。末尾 $j$ 個がすべて前半由来となる確率は $(k - j 2 k - j) / (k 2 k) = \frac{k ( k - 1 ) \dots ( k - j + 1 )}{2 k ( 2 k - 1 ) \dots ( 2 k - j + 1 )}$ 。後半由来についても同様。
計算すると、 $\sum_{j \geq 1} (k - j 2 k - j) = (k - 1 2 k)$ なので（ホッケースティック恒等式）、前半由来の側の期待値は $(k - 1 2 k) / (k 2 k) = \frac{k}{k + 1}$ 。後半由来の側も同じ。よって $E [R] = \frac{2 k}{k + 1}$ 。

したがって $E [C_{k}] = 2 k - \frac{2 k}{k + 1} = \frac{2 k ^{2}}{k + 1}$ 。
検算: $k = 1$ で $1$ （比較 1 回）で一致。 $k = 2$ で $8/3$ : 4 要素のうち前半 2 個・後半 2 個の混ざり方 6 通りで比較回数は 3,3,3,3,2,2 なので平均 $16/6 = 8/3$ で一致。

配列の長さ 8 のマージソート:
- 長さ 1 の 2 つをマージ: $k = 1$ が 4 回、各 $1$ → 計 $4$
- 長さ 2 の 2 つをマージ: $k = 2$ が 2 回、各 $8/3$ → 計 $16/3$
- 長さ 4 の 2 つをマージ: $k = 4$ が 1 回、 $32/5$

前半・後半は独立に一様な相対順序をもつので、期待値の線形性から合計は
$4 + \frac{16}{3} + \frac{32}{5} = \frac{60 + 80 + 96}{15} = \frac{236}{15}$ 。
（最悪 17 回より小さく妥当。）

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる