php 两种方式实现求 斐波那契数

1. 使用递归方式。

    //使用递归方式求斐波那契数 ???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 两种方式实现求 斐波那契数

原文地址：https://www.cnblogs.com/babytuo/p/8986296.html