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}
これで示せる。

ユークリッドの互除法

 1.4.1で扱われているユークリッドの互除法の計算回数について調べた。
ラメの定理 a,b∈自然数(0を含む), a>b, mをbの桁数, nをユークリッドの互除法で余りを求めた回数とする。このとき 5m >= n となる。
 証明には1.4.2で扱われているフィボナッチ数が重用な役割を演ずる。具体的に言うと、b >= f_(n+1)となることを使う。その証明はf_i = f_(i-1) + f_(i-2)とr_i = q_(n-i+1)*r_(n-i+1) + r_(n-i+2)を見比べれば分かる。(q_(n-i+1) >= 1に注意)i=n-1とすれば良い。
 ユークリッドの互除法とラメの定理については
プログラミングの背景:数論
のPDFが参考になった。
 完全に自分用のメモなので無定義語あります。