ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » ハノイの塔とマージソートの分析

2012年4月
« 3月   5月 »
1234567
891011121314
15161718192021
22232425262728
2930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

ハノイの塔とマージソートの分析

再帰呼び出しを含む処理の、速度分析の説明として、ハノイの塔とマージソートを 説明する。

ハノイの塔

ハノイの塔は、3本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。 ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 ということが予想される。

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。 これより、


ということが言える。 ディスクが 枚で、予想が正しいと仮定すると、 枚では、



となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

マージソートの処理速度分析

最も高速なソートアルゴリズムとして、クイックソートがあげられる。 しかし、説明が分かり難いので、同じ処理速度のオーダとなる、 マージソートの分析で説明する。

マージソートのアルゴリズムは、

  • データが1件の時は、そのまま。
  • それ以上の件数では、
    • データを中央で2分割して、それぞれをマージソートを行う。
    • 出来上がった2つのデータ列を、先頭から2つを比較し小さい方から移し替える。

この方式であれば、再帰方程式として、以下の式が示される。


N=1,2,4,8,…と、代入を繰り返すと、処理時間は、 であることがわかる。