ランダム化クイックソートの期待比較回数

定理 5.5（「ソートアルゴリズム」§5）・ ✓公理まで証明済み

相異なる $n$ 個の要素からなる任意の入力に対し、各再帰呼び出しでピボットをその部分配列から一様ランダムに（過去の選択と独立に）選ぶクイックソートの期待比較回数 $\mathbb{E}[C_n]$ は

\mathbb{E}[C_n] \;=\; \sum_{1 \le i < j \le n} \frac{2}{\,j-i+1\,} \;<\; 2n\,(H_n - 1) \;\le\; 2n \ln n

を満たす（左の不等号は $n \ge 2$ のとき。 $n = 1$ では $\mathbb{E}[C_1] = 0$ で両辺とも $0$ になる）。ここで $H_n = \sum_{k=1}^{n} 1/k$ は調和数である。とくに期待実行時間は $O(n\log n)$ である。

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 2 件、定義なども含めて 2 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

証明で明示的に参照している定理は、まだありません。