php求斐波那契數(shù)的兩種實現(xiàn)方式【遞歸與遞推】

本文實例講述了php求斐波那契數(shù)的兩種實現(xiàn)方式。分享給大家供大家參考，具體如下：

斐波那契數(shù)，亦稱之為斐波那契數(shù)列（意大利語： Successione di Fibonacci)，又稱黃金分割數(shù)列、費波那西數(shù)列、費波拿契數(shù)、費氏數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞歸的方法定義：F0=0，F(xiàn)1=1，F(xiàn)n=Fn-1+Fn-2（n>=2，n∈N*），用文字來說，就是斐波那契數(shù)列列由 0 和 1 開始，之后的斐波那契數(shù)列系數(shù)就由之前的兩數(shù)相加。

1 使用遞歸方法。  順著思路去想， f(1)= 1; f(2) = 1 ; f(3) = f(2)+f(1)  【2】  f(4) = f(3)+f(2) 3

//使用遞歸方式求斐波那契數(shù)
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;
}

最后，進行性能分析。

明顯的可以預(yù)測，遞歸方法，每多一層，就要向下遞歸兩次。 約為 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  每往上一個數(shù)約慢兩倍
echo bench_profile($s )."br/>";
//使用遞推算法。
$s = explode(' ',microtime());
echo  bench_profile($s )."br/>";
  echo fb2(35); //使用遞推 時間極短。
echo bench_profile($s )."br/>";

總結(jié)：使用遞歸算法，到求第100 個斐波那契數(shù) 時會卡到機器跑不動，而使用遞推算法，幾乎不費時間。

算法復(fù)雜度是非常重要的概念，也是區(qū)分程序員的一把好尺子。

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運算技巧總結(jié)》

希望本文所述對大家PHP程序設(shè)計有所幫助。