最新消息:

斐波那契数列递归算法优化

未分类 466浏览 0评论

递归一用不慎容易引起性能问题,导致资源过度浪费,甚至死机。

常规实现方式:

<?php

class Test
{
    public $obj;
    public $i;
    
    public function getFB($n){
      if($n == 1 || $n == 2){
          $this->obj[$n] = 1;
          return 1;
        }else {
          $this->obj[$n] = $this->getFB($n-1) + $this->getFB($n-2);
          return $this->obj[$n];
        }
    }
}

$Test = new Test();
var_dump($Test->getFB(30), $Test->i);

注意传入值是30,更大值已经承受不住,输出结果:

int(832040)
int(1664079)

优化后算法:

<?php

class Test
{
    public $i = 0;//声明一个变量i,记录调用getFB这个函数的次数.
    
    public $obj = [];//声明一个对象obj,用来保存已经求过的项.
	
    public function getFB($n){
      $this->i++;
      //求n位是多少,就先去obj里面看看,之前求过没有,如果之前求过,就直接取出来使用.
      if(isset($this->obj[$n])){
        //如果进到了这里,说明当前这个n位已经求过,已经存进obj里面了
        return $this->obj[$n];
      }else {
        //如果进到这里来了,就说明当前这个n位之前没求过,没求过就求呗.
        if($n == 1 || $n == 2){
          $this->obj[$n] = 1;
          return 1;
        }else {
          $this->obj[$n] = $this->getFB($n-1) + $this->getFB($n-2);
          return $this->obj[$n];
        }
      }
    }
	
}

$Test = new Test();
var_dump($Test->getFB(60), $Test->i);

注意是传入值是60,轻轻松松,输出结果:

int(1548008755920)
int(117)

转载请注明:微刻 blog.wecot.cn » 斐波那契数列递归算法优化

发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (1)

  1. 亲手活捉大佬一只
    丘八2年前 (2019-02-26)回复