php求斐波那契数的两种实现方式【递归与递推】

php  /  管理员 发布于 7年前   192

本文实例讲述了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 )."
";  echo fb(35); //使用递归 耗时 40.925 sec  每往上一个数约慢两倍echo bench_profile($s )."
";//使用递推算法。$s = explode(' ',microtime());echo  bench_profile($s )."
";  echo fb2(35); //使用递推 时间极短。echo bench_profile($s )."
";

总结：使用递归算法，到求第100 个斐波那契数 时会卡到机器跑不动，而使用递推算法，几乎不费时间。

算法复杂度是非常重要的概念，也是区分程序员的一把好尺子。

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

您可能感兴趣的文章:

• php实现斐波那契数列的简单写法
• php处理斐波那契数列非递归方法
• php实现斐波那契数列代码分享
• php递归使用示例(php递归函数)
• php实现递归的三种基本方式
• php实现无限级分类查询（递归、非递归）
• PHP经典算法集锦【经典收藏】
• PHP面试常用算法(推荐)
• 使用PHP实现二分查找算法代码分享
• PHP常用算法和数据结构示例(必看篇)