ソートと探索比較ソートの計算量・下界・二分探索・ハッシュ

比較だけで並べ替えるソートは、最悪時に $\lceil \log_2 n! \rceil = \Theta(n \log n)$ 回以上の比較が必要で、マージソートとヒープソートはこの下界を定数倍の範囲で達成する。クイックソートは最悪 $\Theta(n^2)$ だが、入力がランダムな順列なら平均比較回数は $2(n+1)H_n - 4n \approx 1.39\, n \log_2 n$ になる。整列済みの配列は二分探索で $\lfloor \log_2 n \rfloor + 1$ 回以下の比較で探せ、ハッシュ表は負荷率が定数なら期待 $O(1)$ で探索できる。

アルゴリズムとデータ構造の第2単元（全4単元）。先に読む単元：計算量と漸化式

情報系院試の問題集・ロードマップ

東大情報理工・東京科学大・阪大の大学別に、出題マップと類題を1冊にした教材（各4,980円）。収録内容と見本を商品ページで確認できる。

情報系の教材を見る

比較ソート・安定性・逆転数の定義

定義

比較ソート

要素どうしの大小比較 $a_i \le a_j$ の結果だけを使って並べ替えるアルゴリズムを比較ソートという。挿入・マージ・クイック・ヒープソートは比較ソートである。計数ソートや基数ソートは、キーが $0$ 以上 $k$ 未満の整数であることを使うので比較ソートではない。

定義

安定性とその場ソート

キーが等しい要素の相対順序が、整列後も入力と同じに保たれるソートを安定なソートという。入力の配列のほかに $O(1)$ （流儀により $O(\log n)$ まで）の作業領域しか使わないものをその場（in-place）ソートという。

定義

逆転数

列 $a_1, \dots, a_n$ で $i < j$ かつ $a_i > a_j$ となる組 $(i, j)$ を逆転といい、その個数を逆転数 $\operatorname{inv}(a)$ という。 $0 \le \operatorname{inv}(a) \le n(n-1)/2$ で、隣どうしの交換1回で逆転数はちょうど1変わる。

代表的なソートの手順と計算量

挿入ソート（配列 $A[1..n]$ ）の手順は次のとおり。

$i = 2, \dots, n$ の順に、 $x = A[i]$ を取り出す。
$j = i - 1$ から左へ、 $A[j] > x$ である間 $A[j+1] \leftarrow A[j]$ と右へずらす。
止まった位置の右 $A[j+1]$ に $x$ を入れる。

マージソートは配列を半分に分けて再帰的に整列し、整列済みの2列を先頭から比べて併合する。長さ $p$ と $q$ の列の併合は $p + q - 1$ 回以下の比較で済む。クイックソートは基準値（ピボット）を1つ選び、それより小さい要素と大きい要素に分割してから、それぞれを再帰的に整列する。ヒープソートは配列を最大ヒープに組み直し（ $O(n)$ ）、根の取り出しと修復（各 $O(\log n)$ ）を $n - 1$ 回繰り返す。

計算量と性質（ $n$ 要素、比較回数で数える）

挿入ソート: $\text{最良 } \Theta(n),\quad \text{最悪・平均 } \Theta(n^2),\quad \text{安定},\ \text{その場}$
比較回数は $\operatorname{inv}(a)$ 以上 $\operatorname{inv}(a) + n - 1$ 以下。
マージソート: $\text{最悪・平均 } \Theta(n \log n),\quad \text{安定},\ \text{作業領域 } \Theta(n)$
最悪の比較回数は $W(n) = W(\lfloor n/2 \rfloor) + W(\lceil n/2 \rceil) + n - 1$ 、 $n = 2^k$ なら $n \log_2 n - n + 1$ 。
クイックソート: $\text{最悪 } \Theta(n^2),\quad \text{平均 } \Theta(n \log n),\quad \text{不安定}$
最悪は整列済みの入力で先頭をピボットにしたときなどに起き、比較回数は $n(n-1)/2$ 。
ヒープソート: $\text{最悪・平均 } \Theta(n \log n),\quad \text{不安定},\ \text{その場}$
計数ソート: $\Theta(n + k),\quad \text{キーは } 0, \dots, k-1 \text{ の整数},\ \text{安定}$
比較を使わないので下界 $\Omega(n \log n)$ の対象外。

比較ソートの下界とクイックソートの平均

定理・法則

比較ソートの下界

条件

相異なる $n$ 個のキーを、比較の結果だけを使って並べ替える決定的なアルゴリズム。

主張

最悪時の比較回数は $\lceil \log_2 n! \rceil$ 以上で、 $\log_2 n! = \Theta(n\log n)$ から $\Omega(n \log n)$ である。ランダムな順列に対する平均の比較回数も $\log_2 n!$ 以上になる。

要点

アルゴリズムを決定木で表すと、 $n!$ 通りの入力順はそれぞれ別の葉に着く必要がある。高さ $h$ の二分木の葉は $2^h$ 個以下なので $2^h \ge n!$ 。キーの範囲を使う計数ソートや基数ソートには当てはまらない。

定理・法則

クイックソートの平均比較回数

条件

相異なる $n$ 個のキーで、入力の $n!$ 通りの順序が等確率（またはピボットを一様ランダムに選ぶ）。分割では、ピボットを残りの $m - 1$ 個と1回ずつ比べる。

主張

C(n) = 2(n+1)H_n - 4n, \qquad H_n = \sum_{k=1}^{n} \frac{1}{k}

で、 $C(n) = 2n \ln n + O(n) \approx 1.39\, n \log_2 n$ 。

要点

整列後に $i$ 番目と $j$ 番目（ $i < j$ ）の要素が比較されるのは、その間の $j - i + 1$ 個から最初にピボットに選ばれるのが両端のどちらかのときで、確率は $2/(j - i + 1)$ 。これを全組で足すと上の式になる。

比較回数を数える計算例

計算例

マージソートの比較回数

$(5, 2, 4, 7, 1, 3, 2, 6)$ をマージソートで整列し、比較回数を数えよ。併合では左右の先頭を比べ、等しいときは左を先に出す。

解答

長さ1の列どうしの併合が4回で、比較は各1回、計4回。 $(2,5)$ 、 $(4,7)$ 、 $(1,3)$ 、 $(2,6)$ ができる。

長さ2どうしの併合は2回。 $(2,5)$ と $(4,7)$ の併合は $2$ 対 $4$ 、 $5$ 対 $4$ 、 $5$ 対 $7$ の3回で $(2,4,5,7)$ 。 $(1,3)$ と $(2,6)$ も3回で $(1,2,3,6)$ 。計6回。

最後の併合は、左に $7$ が残るまで比べ続けるので $4 + 4 - 1 = 7$ 回で $(1,2,2,3,4,5,6,7)$ 。合計 $4 + 6 + 7 = 17$ 回。

検算

$n = 8$ の最悪の比較回数 $n\log_2 n - n + 1 = 24 - 8 + 1 = 17$ と一致し、下界 $\lceil \log_2 8! \rceil = \lceil \log_2 40320 \rceil = 16$ 以上である。等しい $2$ は入力で前にあったほうが前に残る（安定）。

計算例

挿入ソートの比較回数と逆転数

$(5, 2, 4, 6, 1, 3)$ を挿入ソートで整列したときの、比較回数と要素の移動（右へずらす）回数を求めよ。

解答

逆転は $(5,2), (5,4), (5,1), (5,3), (2,1), (4,1), (4,3), (6,1), (6,3)$ の9個で、右へずらす回数は逆転数に等しく9回。比較は、ずらすたびに1回と、 $A[j] \le x$ で止まるときの1回である。左端まで動いて比較なしで止まるのは $2$ と $1$ を入れるときで、止まるための比較は $5 - 2 = 3$ 回。比較回数は $9 + 3 = 12$ 回。

検算

比較回数は $\operatorname{inv} = 9$ 以上、 $\operatorname{inv} + n - 1 = 14$ 以下に入る。実装して数えても比較12回、移動9回になる。

計算例

$n = 3$ でのクイックソートの平均

相異なる3要素のランダムな順列を、先頭をピボットとするクイックソートで整列する。平均比較回数を求めよ。

解答

最初の分割で比較は2回。ピボットが中央値なら（確率 $1/3$ ）左右が1要素ずつで追加の比較はない。最小か最大なら（確率 $2/3$ ）残り2要素の整列に1回かかる。平均は

2 + \frac{2}{3} \cdot 1 = \frac{8}{3}

検算

公式で $2 \cdot 4 \cdot H_3 - 12 = 8 \cdot \dfrac{11}{6} - 12 = \dfrac{8}{3}$ 。 $3! = 6$ 通りを全部数えても比較回数の合計は16で、平均 $16/6 = 8/3$ 。 $n = 4$ でも全24通りの平均 $29/6$ が公式と一致する。

二分探索・二分探索木・ハッシュ法の計算量

整列済み配列 $A[0..n-1]$ から値 $t$ を探す二分探索の手順は次のとおり。

$lo = 0$ 、 $hi = n - 1$ とする。
$lo \le hi$ の間、 $m = \lfloor (lo + hi)/2 \rfloor$ として $A[m]$ と $t$ を比べる。
等しければ $m$ を返す。 $A[m] < t$ なら $lo = m + 1$ 、 $A[m] > t$ なら $hi = m - 1$ として2へ戻る。
$lo > hi$ になったら「見つからない」を返す。

定理・法則

二分探索の比較回数

条件

長さ $n \ge 1$ の整列済み配列。 $A[m]$ と $t$ の三方向の比較（小・等・大）を1回と数える。

主張

どの $t$ に対しても、比較は $\lfloor \log_2 n \rfloor + 1$ 回以下で終わる。計算量は $\Theta(\log n)$ 。

要点

1回の比較で、残る範囲の長さ $\ell$ が $\lfloor \ell/2 \rfloor$ 以下になる。配列が整列していないと使えない。

計算例

二分探索の手順を追う

$A = (2, 5, 8, 12, 16, 23, 38, 56, 72, 91)$ （添字0から）で $t = 23$ を探せ。

解答

$(lo, hi) = (0, 9)$ で $m = 4$ 、 $A[4] = 16 < 23$ なので $lo = 5$ 。 $(5, 9)$ で $m = 7$ 、 $A[7] = 56 > 23$ なので $hi = 6$ 。 $(5, 6)$ で $m = 5$ 、 $A[5] = 23$ で見つかる。比較は3回。

検算

上限 $\lfloor \log_2 10 \rfloor + 1 = 4$ 回以下に収まる。

探索のデータ構造

二分探索木: $\text{探索・挿入・削除 } O(h), \qquad \lfloor \log_2 n \rfloor \le h \le n - 1$
$h$ は木の高さ。各節点で、左部分木のキーは節点より小さく、右部分木のキーは大きい。整列済みの順で挿入すると $h = n - 1$ になる。赤黒木などの平衡木は $h = O(\log n)$ を保つ。
連鎖法のハッシュ表: $\alpha = \frac{n}{m}, \qquad \text{失敗する探索の期待 } \Theta(1 + \alpha)$
$m$ はバケット数。各キーが独立に一様なバケットへ写る（単純一様ハッシュ）と仮定する。成功する探索で調べる要素数の期待値は $1 + \alpha/2 - \alpha/(2n)$ 。
開番地法（一様ハッシュ）: $\text{失敗する探索の期待探査回数} \le \frac{1}{1 - \alpha} \quad (\alpha < 1)$

答案でよくある誤り

1
「どんなソートも $\Omega(n \log n)$ 」と書く。下界は比較ソートについての定理で、キーが小さな整数なら計数ソートは $\Theta(n + k)$ で整列できる。
2
クイックソートの計算量を $O(n \log n)$ とだけ書く。最悪は $\Theta(n^2)$ で、 $\Theta(n\log n)$ は平均（ランダムな入力またはランダムなピボット）の評価である。どちらの意味かを書く。
3
マージソートをその場ソートとして扱う。配列の標準的な実装は $\Theta(n)$ の作業領域を使う。
4
併合で等しいキーのとき右を先に出し、安定性を失う。等しいときは左の列から出す。
5
二分探索で $m = (lo + hi)/2$ を整数にしない、または $hi = m$ として範囲が縮まらず止まらない。 $m$ を切り捨て、 $lo = m + 1$ 、 $hi = m - 1$ で必ず範囲を狭める。
6
二分探索木の探索を常に $O(\log n)$ とする。平衡を保たない木では高さが $n - 1$ になり得るので $O(h)$ と書き、最悪 $\Theta(n)$ を区別する。