NAHA

記録帳

比較を用いたソートの計算量の下界

　2.4のソーティングの計算量の下界について。
　入力要素数をn、ソートに対応した2分決定木の深さをhとすると
{ \displaystyle 2^h \geq n! }
これより
{ \displaystyle h \geq \log{n!} \geq \frac{1}{2} n \log{n} }
となり、Ω(nlogn)が示される。
　さて、最後の不等式の証明は通常Stirlngの公式を使うみたいですが、Stirlingの公式を忘れてたので（数学馬鹿）使わずに証明した。簡単のためnは2以上の偶数とする。
\begin{eqnarray} \log{n!} & = & \log{1} + \log{2} + \cdots + \log{(n - 1)} + \log{n} \\ & = & (\log{1} + \log{n}) + (\log{2} + \log{(n - 1)}) + \cdots \\ & = & \log{n} + \log{ \{ 2(n - 1) \} } + \cdots \\ & \geq & \log{n} + \log{n} + \cdots \\ & = & \frac{1}{2} n \log{n} \end{eqnarray}
これで示せる。