QuickSort()関数が最初に呼び出されたときの比較
lower<=upper&&data[lower]<=div
lower<=upper&&data[upper]>div
の実行回数
は、
![$ N+1$](img2.png)
回である。そして、再帰
呼び出しにより、
![$ \alpha$](img3.png)
個と
![$ \beta$](img4.png)
個の場合の
QuickSort()が呼び出されることにな
る。
![$ N$](img5.png)
個の時のトータルの比較回数を
![$ a_N$](img6.png)
として、これらの関係は、
![$\displaystyle a_N=N+1+a_\alpha+a_\beta$](img7.png) |
(1) |
となる。もちろん、
![$ \alpha$](img3.png)
と
![$ \beta$](img4.png)
は、
![$ 1$](img8.png)
〜
![$ N-1$](img9.png)
の値を取りうる。そして、
sort[]に格納されている値がランダムであれば、同じ確率で
![$ 1$](img8.png)
〜
![$ N-1$](img9.png)
の値をとる。さ
らに、
![$ \alpha$](img3.png)
と
![$ \beta$](img4.png)
の和は
![$ N$](img5.png)
になることはクイックソートのアルゴリズムから自明
である。したがって、
![$ a_N$](img6.png)
の期待値は、
となる。この漸化式から、
![$ a_N$](img6.png)
を求めることになるが、計算は結構大変である。まず、
式(
2)を
と変形しておく。つぎに、この式の
![$ N$](img5.png)
を
![$ N-1$](img9.png)
にした場合の式
を利用する。式(
3)から式(
4)の辺々を差し引いて整理す
ると、
![$\displaystyle (N-1)a_N-(N-2)a_{N-1}$](img15.png) |
![$\displaystyle =(N+1)(N-1)-N(N-2)+2a_{N-1}$](img16.png) |
(5) |
となる。さらに、整理を進めると
![$\displaystyle (N-1)a_N-Na_{N-1}$](img17.png) |
![$\displaystyle =2N-1$](img18.png) |
(6) |
となる。両辺を、
![$ (N-1)N$](img19.png)
で割ると、
となる。ここで、
![$ a_N/N$](img23.png)
を
![$ b_N$](img24.png)
と置くと、
![$\displaystyle b_N-b_{N-1}=\frac{1}{N}+\frac{1}{N-1}$](img25.png) |
(8) |
となり、階差数列を用いて容易に計算できる。すなわち、
![$\displaystyle b_N=b_2+\sum_{k=3}^N\left(\frac{1}{k}+\frac{1}{k-1}\right)$](img26.png) |
(9) |
である。
![$ a_2=3$](img27.png)
より、
![$ b_2=3/2$](img28.png)
となるので、
となる。ここで、
![$ N$](img5.png)
が大きい場合、
![$ \sum_{k=1}^N\frac{1}{k}$](img33.png)
は
![$ \log_eN+\gamma$](img34.png)
に近
づくことが知られている
4。
![$ \gamma$](img36.png)
はオイラー数と言われる定数で、その値は0.577
![$ \cdots$](img37.png)
である。したがって、
![$ N$](img5.png)
が大きい場合、
![$\displaystyle b_N\simeq-\frac{3}{2}-\frac{1}{N}+2(\log_eN+\gamma)$](img38.png) |
(11) |
となる。右辺の
![$ \log_eN$](img39.png)
は他の項に比べて大きな値を取る
5。したがって、
![$\displaystyle b_N\simeq 2\log_eN$](img42.png) |
(12) |
となる。
![$ b_N$](img24.png)
の定義から、
![$\displaystyle a_N \simeq 2N\log_eN$](img43.png) |
(13) |
となる。
はsort[]の要素の比較回数を表す。したがって、
が大きい場合の比較回数は、
となる。
ホームページ:
Yamamoto's laboratory著者:
山本昌志
Yamamoto Masashi
平成17年10月27日