フィボナッチ数 Fibonacci Number

Time-Space complexity など、動的計画法と再帰による手法の違いを表すよい例がイタリアの数学者フィボナッチによって定義されたフィボナッチ数(Fibonacci number)の生成です。n 番目のフィボナッチ数 F_n は

F_n = F_n-1 + F_n-2

と定義されます。

これはフィボナッチがウサギの増殖をモデル化するために定義した数です。フィボナッチは、もし１年目に１つがいのウサギがいれば、ｎ年目に生まれるウサギのつがいの数は、その１年前と２年前のウサギのつがいの和に等しいと推量しました。従ってフィボナッチ数列の最初の数項は F₀ = 0, F₁ = 1 とすれば
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
.
.
となります。この数列は、自然界の現象やアプリケーションにも数多く出現します。

フィボナッチ数列は再帰的な式で定義できるので、それを以下のように簡単な再帰的なプログラムとして記述することができます。

001 int fibonacci( int i ){
002     if ( i == 0 ) return 0;
003     if ( i == 1 ) return 1;
004     return fibonacci(i - 2) + fibonacci(i - 1);
005 }

しかし、単純な再帰によるプログラムの計算量は指数関数時間になってしまいます。例えば、フィボナッチ数列の第5項を再帰で求めると以下のようになります。




このように、最終的にはF(n)の結果がF(0)とF(1)の呼び出し回数の和になってしまいます。


以下のように、動的計画法を用いればF(n)をO(n)の多項式時間の計算量で求めることができます。

001 int F[MAX];
002 
003 void makeFibonacci(){
004     F[0] = 0;
005     F[1] = 1;
006     for ( int i = 2; i < MAX; i++ ){
007         F[i] = F[i-2] + F[i-1];
008     }
009 }

動的計画法では全ての数列の値をメモリに記憶します。このプログラムはフィボナッチ数を小さい方から生成し記録していくので、F(i)を計算するときにはF(i-1)とF(i-2)がすでに計算されているのでそれを有効利用することができます。このように、小さい問題の解をメモリに記憶することにより、指数関数時間を多項式時間に改善し、計算時間を飛躍的に減少させることができます。