乱択クイックソート・乱択選択の期待比較回数

ピボットの選び方で場合分けして期待比較回数の漸化式を立て（全期待値の公式）、乱択クイックソート・乱択クイックセレクトの比較回数の期待値を小さい $n$ で求められる

前提

指示変数と期待値の線形性（大学数学アルゴリズムと計算量）
条件付き分布と全期待値の公式（大学数学確率・統計）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
期待値（数学A 場合の数と確率）
確率変数と確率分布（数学B 統計的な推測）
平均と合計（算数いろいろな文章題）
平均値・中央値・最頻値（中学数学データの活用）
代表値（平均値・中央値・最頻値）（数学I データの分析）
分散と標準偏差（数学I データの分析）
変量の変換と平均・分散（数学I データの分析）
確率変数の期待値・分散と $a X + b$ （数学B 統計的な推測）
確率変数の和と積（独立な場合）（数学B 統計的な推測）
指示変数と期待値の線形性（大学数学アルゴリズムと計算量）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
多項式の不定積分（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
$sin x / x$ の極限（数学III 極限）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
三角関数の導関数（数学III 微分法）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
基本的な関数の不定積分（数学III 積分法）
置換積分（数学III 積分法）
部分積分（数学III 積分法）
定積分の計算（数学II 微分法と積分法）
定積分の置換・部分積分と偶関数・奇関数（数学III 積分法）
重積分と累次積分（大学数学微分積分）
同時分布・周辺分布と独立性（大学数学確率・統計）
条件付き確率と乗法定理（数学A 場合の数と確率）
条件付き分布と全期待値の公式（大学数学確率・統計）

説明

要素がすべて異なる長さ $n$ の列を、ピボット（基準の要素）を一様ランダムに選んで分割する乱択クイックソートや乱択クイックセレクト（ $k$ 番目に小さい要素を探す方法）について、要素どうしの比較回数の期待値を求めます。方法は、「ピボットが何番目に小さい要素だったか」で場合分けすることです。こうすると、期待値の漸化式が全期待値の公式から立ちます。あとは $n = 1, 2, 3, \dots$ と小さい順に計算すれば、具体的な期待値が分数で正確に求まります。アルゴリズムの平均的な速さを確かめるときや、実験値と理論値を比べるときに使います。

なぜそうしてよいのか

長さ $n$ の列で、ピボットを $n$ 個の要素から等確率 $\frac{1}{n}$ で選ぶとします。ピボットが小さい方から $r$ 番目の要素であることを「ピボットの順位が $R = r$ 」と書きます。分割では、ピボットを残りの $n - 1$ 個それぞれと 1 回ずつ比べます。これで比較はちょうど $n - 1$ 回です。その結果、列は「ピボットより小さい $r - 1$ 個」と「大きい $n - r$ 個」に分かれ、それぞれについて同じ手続きをくり返します。この先のピボットも新しく一様ランダムに選ばれます。そのため、 $m$ 個の異なる要素からなる部分列での比較回数の分布は、要素の値や並び順によらず個数 $m$ だけで決まります。そこで、その期待値を $C_{m}$ と書くことができ、 $E [比較回数 ∣ R = r] = (n - 1) + C_{r - 1} + C_{n - r}$ となります。

全期待値の公式 $E (X) = E (E (X ∣ R))$ を使い、 $R$ の各値に確率 $\frac{1}{n}$ を掛けて足すと $C_{n} = (n - 1) + \frac{1}{n} \sum_{r = 1}^{n} (C_{r - 1} + C_{n - r})$ です。 $r$ が $1$ から $n$ まで動くとき、 $r - 1$ も $n - r$ もちょうど $0, 1, \dots, n - 1$ を 1 回ずつとります。よって $C_{n} = (n - 1) + \frac{2}{n} \sum_{j = 0}^{n - 1} C_{j}$ となります。右辺には $C_{n}$ より小さい添字だけが現れるので、小さい $n$ から順に計算できます。クイックセレクトでは、目標の要素を含む片側だけで手続きを続けます。ピボットがちょうど目標なら、そこで終わります。したがって、部分問題の期待値は 1 つだけ足されます。

答えの検算には指示変数も使えます。小さい方から $i$ 番目と $j$ 番目（ $i < j$ ）の要素が比べられるのは、順位が $i$ 以上 $j$ 以下の $j - i + 1$ 個のうち、最初にピボットに選ばれるのが $i$ 番目か $j$ 番目の要素のときに限られます。その確率は $\frac{2}{j - i + 1}$ です。期待値の線形性から、これらの確率をすべての組 $(i, j)$ について足したものも比較回数の期待値になります。たとえば $n = 3$ では $1 + 1 + \frac{2}{3} = \frac{8}{3}$ となり、漸化式の値と一致します。

手順

比較回数の数え方を確認する：要素はすべて異なるとする。分割 1 回で、ピボットと残りの要素をそれぞれ 1 回ずつ比べるので $n - 1$ 回。要素が 0 個か 1 個のときは比較しない。
ピボットの順位 $R$ （ $P (R = r) = \frac{1}{n}$ , $r = 1, \dots, n$ ）で場合分けし、条件付き期待値を書く。クイックソートでは $E [\cdot ∣ R = r] = (n - 1) + C_{r - 1} + C_{n - r}$ となる。
全期待値の公式で平均する。クイックソートでは $C_{n} = (n - 1) + \frac{2}{n} \sum_{j = 0}^{n - 1} C_{j}$ （ $C_{0} = C_{1} = 0$ ）となる。
クイックセレクトの場合： $k$ 番目に小さい要素を探すときの期待比較回数を $T (n, k)$ とおく。 $r = k$ なら、その場で終わる。 $r > k$ なら左側の $r - 1$ 個で $k$ 番目を探し、 $r < k$ なら右側の $n - r$ 個で $k - r$ 番目を探す。式にすると $T (n, k) = (n - 1) + \frac{1}{n} (\sum_{r = k + 1}^{n} T (r - 1, k) + \sum_{r = 1}^{k - 1} T (n - r, k - r))$ 、 $T (1, 1) = 0$ となる。
初期値から小さい順に漸化式へ代入し、求めたい $n$ まで計算する。必要なら指示変数の和で検算する。

例題

互いに異なる 4 個の数からなる列を乱択クイックソートで整列する。各段階で、その部分列からピボットを一様ランダムに選び、残りの要素すべてと 1 回ずつ比較して分割する。要素が 1 個以下の部分列では比較しない。比較回数の期待値を求めよ。

例題の解答

手順 1： $m$ 個の場合の期待比較回数を $C_{m}$ とおく。比較が起こらないので $C_{0} = C_{1} = 0$ である。

手順 2・3：ピボットの順位で場合分けし、全期待値の公式で平均すると $C_{n} = (n - 1) + \frac{2}{n} \sum_{j = 0}^{n - 1} C_{j}$ が得られる。

手順 5：小さい順に計算する。
- $n = 2$ ： $C_{2} = 1 + \frac{2}{2} (C_{0} + C_{1}) = 1$ 。
- $n = 3$ ： $C_{3} = 2 + \frac{2}{3} (C_{0} + C_{1} + C_{2}) = 2 + \frac{2}{3} \cdot 1 = \frac{8}{3}$ 。
- $n = 4$ ： $C_{4} = 3 + \frac{2}{4} (0 + 0 + 1 + \frac{8}{3}) = 3 + \frac{1}{2} \cdot \frac{11}{3} = 3 + \frac{11}{6} = \frac{29}{6}$ 。

検算：組 $(i, j)$ が比べられる確率は $\frac{2}{j - i + 1}$ である。 $j - i = 1$ の組は 3 つで確率は各 $1$ 、 $j - i = 2$ の組は 2 つで各 $\frac{2}{3}$ 、 $j - i = 3$ の組は 1 つで $\frac{1}{2}$ 。合計は $3 + \frac{4}{3} + \frac{1}{2} = \frac{29}{6}$ となり、漸化式の値と一致する。

答え: $\frac{29}{6}$

よくある誤り

分割 1 回の比較回数を $n$ 回と数えてしまう誤り。ピボット自身とは比べないので、正しくは $n - 1$ 回です。 $C_{2} = 2$ ではなく $C_{2} = 1$ になります。
両側の部分問題を足し忘れて $C_{n} = (n - 1) + \frac{1}{n} \sum_{j = 0}^{n - 1} C_{j}$ としてしまう誤り。 $C_{r - 1}$ と $C_{n - r}$ の両方が加わるので、正しくは係数が $\frac{2}{n}$ です。この誤りだと $C_{3} = 2 + \frac{1}{3} = \frac{7}{3}$ になりますが、正しくは $\frac{8}{3}$ です。
平均の大きさをそのまま代入して $C_{n} = (n - 1) + 2 C_{(n - 1) /2}$ のように計算してしまう誤り。一般に $E [C_{R - 1}]$ と $C_{E [R - 1]}$ は等しくありません。正しくは、各 $r$ ごとの値を確率 $\frac{1}{n}$ で平均します。 $n = 3$ でこの誤りを犯すと $2 + 2 C_{1} = 2$ になりますが、正しくは $\frac{8}{3}$ です。
クイックセレクトで両側を再帰したり、右側に進むときの順位をずらし忘れて $T (n - r, k)$ としてしまう誤り。正しくは、目標を含む片側だけに進みます。右側では $T (n - r, k - r)$ 、左側では $T (r - 1, k)$ です。 $r = k$ のときは 0 を足します。例えば $T (3, 1) = 2 + \frac{1}{3} (0 + 0 + 1) = \frac{7}{3}$ です。

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

入口の問題

この技能を使う問題

難易度 3（期末試験の応用レベル）
互いに異なる $5$ 個の数が入った配列から、小さい方から $3$ 番目の数（中央値）を、次の乱択選択アルゴリズム（乱択クイックセレクト）で求める。
- 現在の候補の集合を $X$ とし、最初は $X$ を $5$ 個の数全体とする。また、求めたい順位を $k = 3$ とする。
- $X$ の要素が $1$ 個だけなら、それを答えとして終了する（比較は行わない）。
- そうでなければ、 $X$ の要素から $1$ つを等確率で選んでピボット $p$ とし、 $p$ を $X$ のほかのすべての要素と $1$ 回ずつ比較して、 $p$ より小さい要素の集合 $L$ と大きい要素の集合 $R$ に分ける（このとき比較は $∣ X ∣ - 1$ 回行われる）。
- $∣ L ∣ = k - 1$ なら $p$ を答えとして終了する。
- $∣ L ∣ \geq k$ なら、 $X$ を $L$ に置き換えて（ $k$ はそのまま）最初の手順に戻る。
- $∣ L ∣ \leq k - 2$ なら、 $X$ を $R$ に、 $k$ を $k - ∣ L ∣ - 1$ に置き換えて最初の手順に戻る。
ピボットの選択は毎回独立に行われるものとする。このアルゴリズムが終了するまでに行う比較の回数の期待値を求めよ。