再帰方程式

再帰を含む処理の処理速度の見積りの例として、 階乗の再帰の速度見積り、2分探索の再帰版の速度見積り、 ハノイの塔の処理速度の速度見積りを示す。

ハノイの塔の再帰方程式と数学的機能法

N枚の板の移動は、以下の手順で実行するため、移動回数を H(N) で表すと、 以下のような再帰方程式が示される。

  • 底の1枚を残して、N-1枚を一旦別の柱に移し、
  • 底の1枚を目的の柱に移動、
  • 別の柱に移しておいた N-1枚を移動、
  H(1) = 1               (N=1の時)
  H(N) = 1 + 2 * H(N-1)  (N>1の時)

少ない枚数のハノイの塔を解くと、処理速度 H(N) では、以下の仮定が成り立つ。

  H(N) = 2^N - 1

よって、数学的帰納法で証明すると、

・H(1) で、仮定が正しいのは明らか。
N = k の時、仮定が正しいならば、 N=k+1の時、
・H(k+1) = 1 + 2 * H(k)         # ルールより
         = 1 + 2 * (2^k - 1)    # N=kの時の仮定を代入
         = 1 + 2^(k+1) - 2
         = 2^(k+1) - 1
であり、仮定は k+1 でも成り立つ。
よって数学的帰納法により、N≧1で成り立つ。

フィボナッチ数の再帰プログラムの処理速度の見積り

講義では、フィボナッチ数の処理速度の見積りは示さなかったが、 自主的な取り組みをしてみることと伝えておいた。 ここで、ヒントを示す。

フィボナッチ数の再帰処理より、成り立つ再帰方程式
   T(1) = Ta
   T(2) = Ta
   T(N) = Tb + T(N-1) + T(N-2)
代入法による一般式の予測
   T(1) = Ta , T(2) = Ta
   T(3) = Tb + Ta + Ta
   T(4) = Tb + (Tb + 2Ta) + Ta = 2Tb + 3Ta
   T(5) = Tb + (2Tb+3Ta) + (Tb+2Ta) = 4Tb + 5Ta
以下の一般式を仮定する。
   T(N) = (Ta + Tb) * fib(N) - Tb
上記一般式は、N=1,2 で仮定が成り立つのは明らか。
N≦k で仮定が成り立つとすれば、N=k+1 の時、
   T(k+1) = Tb + T(k) + T(k-1)
          = Tb + {(Ta + Tb) * fib(k) - Tb} + {(Ta + Tb) * fib(k-1) - Tb}
          = (Ta + Tb){ fib(k) + fib(k-1) } - Tb
          = (Ta + Tb) * fib(k+1) - Tb
よって、k+1 でも仮定が成り立つことが確認できた。

この一般式より、フィボナッチ数の再帰呼出し処理の速度のオーダーは、 ) となる。 ビネの公式より、 )

fib(N) = [ {(1+sqrt(5))/2}^N - {(1-sqrt(5))/2}^N ] / sqrt(5)

# くそ、授業中に記憶だけで書いた(1+sqrt(5))/2 の値が違ってた....
 

2015年12月

    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

アーカイブ

Google

このブログ記事について

このページは、T-Saitohが2005年5月10日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「体が筋肉痛...」です。

次のブログ記事は「体育祭、ご苦労さまでした。」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。