PHPでフィボナッチ数列をつくってみる
http://qiita.com/zss_tr/items/2a7625b2d2188538adbc
この書き方はフィボナッチ数の定義ですが、そのまま実装すると非常に効率が悪く、実用にはなりません。
<?php
// by satosystems
// http://d.hatena.ne.jp/satosystems/20121228/1356655565
function fib1($n){
if ($n < 2){ return $n; }
return fib1($n - 2) + fib1($n - 1);
}
// by Dan Kogai
// http://blog.livedoor.jp/dankogai/archives/50958771.html
function fib2($n){
if($n < 2){return $n;}
return fib2_sub(1, 1, $n);
}
function fib2_sub($a, $b, $c){
if ($c <= 2){ return $a; }
return fib2_sub($a+$b, $a, $c-1);
}
// by NurseAngel
function fib3($n){
$fib0 = 0;
$fib1 = 1;
$ret = 0;
for($i=0; $i<$n; $i++){
$ret = $fib1;
$fib1 = $fib0 + $fib1;
$fib0 = $ret;
}
return $ret;
}
// by C言語による最新アルゴリズム事典
function fib4($n){
return floor( pow((1+sqrt(5))/2, $n) / sqrt(5) + 1/2 );
}
| 関数 | 処理時間 | F(38)の値 |
|---|---|---|
| fib1() | 34.29149秒 | 39088169 |
| fib2() | 0.00005秒 | 39088169 |
| fib3() | 0.00002秒 | 39088169 |
| fib4() | 0.00002秒 | 39088169 |
fib1はフィボナッチ数列の定義そのものです。
何も考えずに実装したらこうなることでしょう。
しかしこちらは、計算時に自分自身を2回呼び出します。
つまり引数が1増えるにつれ、fib1()を呼び出す回数がおよそ2倍になります。
計算量はO(2n)となり、効率の非常に悪いオーダーです。
fib1(100)なんて求めようとすると、早々と反応がなくなってしまいます。
fib2は少々わかりにくいですが、上から順ではなく下から計算しています。
fib2_sub()の1回目に与えている1,1という引数は、順にF2、F1の計算結果です。
あとはfib2_sub()の再帰呼び出しで計算します。
fib2_sub()の2回目の引数はF2+F1つまりF3、F2、数値の37です。
fib2_sub()の3回目の引数はF3+F2つまりF4、F3、数値の36です。
…と順に下っていき、最後のfib2_sub()の引数はF38、F37、数値の2となります。
これによって引数が1増えても、fib2()の呼び出しは1回しか増えません。
計算量はO(n)となり、劇的に改善どころかとんでもない速度になりました。
というかこの時点で早すぎてfib2(38)では計算する意味がないレベル。
fib2(1000)でも余裕で計算可能です。
正直既にこの時点で終わりでいいんじゃね、という気もしますが、よく見てみたらfib2_sub()の再帰って実は計算には全く使わず、単にループ回数をカウントしてるだけです。
カウントしてるだけならループでいいだろう、ということでfib3()です。
こちらも単純に下から足してるだけで、やってることはfib2()とほぼ同じです。
ただ再帰の関数呼び出しが無くなったせいか、速度もさらに上がっています。
さて、実は再帰もループも使わずにフィボナッチ数を一発で求める公式が存在します。
Fn = \frac{ \phi^n - \left(-\phi \right)^{-n} }{ \sqrt{5} } = \left[ \frac{ \phi^n }{ \sqrt{5} } + \frac{1}{2} \right]
ただしφは黄金比
ルートとか割り算とか入ってるくせに計算すると必ず自然数になるとか意味がわからない。
計算量はO(1)でいいのかな、これ？
早すぎてfib3()と違いが分かりませんが、F2000とかを求めようとするとfib4()のほうが早くなるようです。
どちらにしろ0.1秒以下なので実用上はほとんど変わらないレベルですが。
まあともかく、結論としては、フィボナッチ数を求めるアルゴリズムでfib1()だけを書いてるサイトは投げ捨ててしまえ、ってことでいいですかね。
※2013/06/07に自サイトに掲載したもの。