本文實例講述了php求斐波那契數的兩種實現方式。分享給大家供大家參考，具體如下：
斐波那契數，亦稱之為斐波那契數列（意大利語： Successione di Fibonacci)，又稱黃金分割數列、費波那西數列、費波拿契數、費氏數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、……在數學上，斐波那契數列以如下被以遞歸的方法定義：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*），用文字來說，就是斐波那契數列列由 0 和 1 開始，之后的斐波那契數列系數就由之前的兩數相加。
1 使用遞歸方法。 順著思路去想， f(1)= 1; f(2) = 1 ; f(3) = f(2)+f(1) 【2】 f(4) = f(3)+f(2) 3
//使用遞歸方式求斐波那契數
public function fb($n){ //
if( $n =2){
return 1;
}else{
return fb($n-1) + fb($n-2);
}
}
2使用遞推方法。
public function fb2($n){ //
if( $n =2){
return 1;
}
$t1 = 1;$t2 = 1;
for($i=3;$i$n;$i++){
$temp = $t1;
$t1 = $t2;
$t2 = $temp + $t2;
}
return $t1 + $t2;
}
最后，進行性能分析。
明顯的可以預測，遞歸方法，每多一層，就要向下遞歸兩次。 約為 O(2 的N次方) 而遞推算法為 O(n),實測代碼如下。
/**性能測試。*/
function bench_profile($starttime , $flag = ''){
$endtime = explode(' ',microtime());
$thistime = $endtime[0]+$endtime[1]-($starttime[0]+$starttime[1]);
$thistime = round($thistime,3);
return $flag."-bench:".$thistime." sec";
}
//使用遞歸算法。
ini_set("max_execution_time" ,3600);
$s = explode(' ',microtime());
echo bench_profile($s )."br/>";
echo fb(35); //使用遞歸 耗時 40.925 sec 每往上一個數約慢兩倍
echo bench_profile($s )."br/>";
//使用遞推算法。
$s = explode(' ',microtime());
echo bench_profile($s )."br/>";
echo fb2(35); //使用遞推 時間極短。
echo bench_profile($s )."br/>";
總結：使用遞歸算法，到求第100 個斐波那契數 時會卡到機器跑不動，而使用遞推算法，幾乎不費時間。
算法復雜度是非常重要的概念，也是區分程序員的一把好尺子。
更多關于PHP相關內容感興趣的讀者可查看本站專題：《PHP數據結構與算法教程》、《php程序設計算法總結》、《php字符串(string)用法總結》、《PHP數組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結》及《PHP數學運算技巧總結》
希望本文所述對大家PHP程序設計有所幫助。
您可能感興趣的文章:- php菜單/評論數據遞歸分級算法的實現方法
- PHP實現無限極分類的兩種方式示例【遞歸和引用方式】
- PHP利用遞歸函數實現無限級分類的方法
- PHP自定義遞歸函數實現數組轉JSON功能【支持GBK編碼】
- PHP遞歸寫入MySQL實現無限級分類數據操作示例
- PHP數組遞歸排序實現方法示例
- PHP迭代與遞歸實現無限級分類
- PHP實現遞歸的三種方法
