クイックソートでの平均比較回数について
佐藤道一
| これは，2005年4月22日の書き下ろしです．7月10日に細かいミスを訂正． 関連ページ 二分探索法の平均探索回数について 二分探索木による探索の平均探索回数について クイックソートで，n 件のデータを整列する場合の計算量（比較回数）は， 平均 O(n log n) (最悪はO(n2)) といったことが，情報処理技術者試験の参考書（但し，第三者が出しているものであって公式参考書はそもそも存在しない）に厳密な証明なしにしばしば書いてある．この点を厳密に述べる． 詳しくは，平均比較回数をμn で表すと， (1) μn ≦ 2 n ln n − (n − 1)/2 (2) μn 〜 2 n ln n （すなわち，左右の比の極限は１） が成り立つ．最悪は n (n − 1)/2 である． （証明）（第１段）n ＝ 1 のときはμ1 ＝ 0 である．n ≧ 2 を固定する．最初の軸について 軸の左がなし，右に n − 1 個となる場合の比較回数の条件付き平均値はμn−1 ＋ (n − 1) 軸の左に１個，右に n − 2 個となる場合の比較回数の条件付き平均値はμ1 ＋ μn−2 ＋ (n − 1) 軸の左に２個，右に n − 3 個となる場合の比較回数の条件付き平均値はμ2 ＋ μn−3 ＋ (n − 1)（2005年7月10日訂正） ： ： 軸の左に j 個，右に n − j − 1 個となる場合の比較回数の条件付き平均値はμj ＋ μn−j−1 ＋ (n − 1)（2005年7月10日訂正） ： ： 軸の右に n − 1 個，左がなしとなる場合の比較回数の条件付き平均値はμn−1 ＋ (n − 1) となり，それぞれ確率 1/n なので，これらの平均をとり μn ＝ (2/n)Σ となる． （第２段）(1) を帰納法で示す．n ＝ 1 のときはμ1 ＝ 0 だから等号で成り立つ．n ≧ 2 を固定し， μj ≦ 2 j ln j − (j − 1)/2 (j ＝ 1, 2, …, n − 1) が成り立つと仮定する．すると， μn ＝ (2/n)Σ μn ≦ (2/n)Σ となる．二分探索木の場合の第２段と同様の方法で， μn ≦ (1/n){n2(2 ln n − 1)} − (1/n){n(n − 1)/2} ＋ (n − 1)/n ＋ n − 1 μn ≦ 2n ln n − n − (n − 1)/2 ＋ 1 ＋ n − 1 μn ＝ 2 n ln n − (n − 1)/2 が得られるので，(1) は示された． （第３段）0 ＜ a ＜ 2 を任意に固定する．このとき，b ＞ 0 を十分大きくとると，すべての n に対して， μn ≧ an ln n − bn (＊) が成り立つことを示そう．a は固定したままで，まず，N を十分大きくとると，すべての n ≧ N に対して −2a ln (n − 1) ＋ (1 − a/2)n/2 ≧ 0 (＊＊) −an/(n − 1) ＋ (1 − a/2)n/2 ≧ 0 (＊＊＊) が成り立つことが，n で割って極限を考えれば分かる．ここで，x ＞ −1 に対して ln (1 ＋ x) ≦ x であることを用いると (＊＊＊) から −an ln {1 ＋ 1/(n − 1)} ＋ (1 − a/2)n/2 ≧ 0 (＊＊＊＊) も得られる．この N を固定する．b ＞ 0 を十分大きくとると，n ＝ 1, 2, …, N に対して (＊) が成り立つ．後は，n ≧ N を固定して， μj ≧ aj ln j − bj が成り立つことを仮定し，今固定した n に対して (＊) が成り立つことを示せばよい． μn ＝ (2/n)Σ μn ≧ (2/n)Σ となる．二分探索木の場合の第４段と同様の方法で， μn ≧ (a/2n)[(n − 1)2{2 ln (n − 1) − 1} ＋ 1] − (2b/n){n(n − 1)/2} ＋ n − 1 μn ＝ a{n − 2 ＋ (1/n)} ln (n − 1) − (a/2){1 − (1/n)}(n − 1) ＋ (a/2) − b(n − 1) ＋ n − 1 μn ≧ a(n − 2) ln (n − 1) − (a/2)(n − 1) − b(n − 1) ＋ n − 1 μn ＝ a(n − 2) ln (n − 1) ＋ {1 − (a/2) − b}n μn ≧ an ln (n − 1) ＋ {1 − (a/2)}n/2 − bn［(＊＊) より］ μn ≧ an ln n − bn［(＊＊＊＊) より］ が得られる． （第４段）第３段と (1) により an ln n − bn ≦ μn ≦ 2 n ln n なので，辺々を n ln n で割り，二分探索木の場合の第５段と同様にして (2) が示される．なお，最悪の場合については軸の片側がない場合を考えればよい． □ |