情報科学 › アルゴリズムとデータ構造 › ソートアルゴリズム

隣接交換のみを使うソートの下界

命題 3.3（「ソートアルゴリズム」§3） ・ ✓公理まで証明済み

配列の要素を動かす操作として、隣接する 2 要素の交換のみを使うアルゴリズムを考える。このとき、入力 aa を昇順に整列するために必要な交換回数は少なくとも inv⁡(a)\operatorname{inv}(a) である。とくに、要素が相異なる長さ nn の入力に対し、最悪の場合 n(n−1)/2n(n-1)/2 回、また一様ランダムな順列に対して平均 n(n−1)/4n(n-1)/4 回の交換が必要であり、どちらも Θ(n2)\Theta(n^2) である。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

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

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

前提をたどる 証明が使う定理・定義（直接 2 件）

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

これを使っている定理

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