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 两种方式实现求 斐波那契数

人吐槽 人点赞

猜你喜欢

发表评论

用户名: 密码:
验证码: 匿名发表

你可以使用这些语言

查看评论:php 两种方式实现求 斐波那契数