为什么这段代码的执行时间会超过30S

[kennedy32]

function tuzi($x){
if($x == 0 || $x == 1){
return 1;
}else{
return tuzi($x-1)+tuzi($x-2);
}
}
function testtuzi($n){
for ($i=0;$i<=$n;$i++){
echo "兔子在".$i."月的数目是".tuzi($i)."<br/>";
}
}
testtuzi(60);

[anheiyouxia]

楼主可以看看这个：http://blog.csdn.net/yuanjilai/article/details/8059580

[flyaway]

斐波拉契数列，递归的方法存在太多的overlapping，大量重复计算，降低了效率

[skydiver]

@TMBest 不是说正确做法是直接用lgamma函数么……

[skydiver]

@skydiver 记错了。。那个是算阶乘。。

[kennedy32]

@Keita1314 额，我只看得懂php

[kennedy32]

@luoyou1014 谢谢

[baiyunheitu]

递归的复杂度不太乐观。

[c742435]

你用一个数组存储计算结果就可以了。算法不用改。

[kuye]

一种很肤浅的作法：
function tuzi($x){
static $result=array();
if(isset($result[$x])){
return $result[$x];
}
if($x == 0 || $x == 1){
$r= 1;
}else{
$r= tuzi($x-1)+tuzi($x-2);
}
$result[$x]=$r;
return $r;
}
function testtuzi($n){
for ($i=0;$i<=$n;$i++){
echo "兔子在".$i."月的数目是".tuzi($i)."<br/>";
}
}
testtuzi(60);

[kevinroot]

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
14896 root 25 0 302m 9.9m 6948 R 100.0 0.5 1:07.71 php tuzi.php

php tuzi.php 11870.42s user 4.86s system 99% cpu 3:18:38.25 total
才跑到46

[dorentus]

回答楼主的问题：

tuzi($x) 这个函数，里面用到了前两次的计算结果 tuzi($x-1) 和 tuzi($x-2)
但是，每次计算的结果并没有保存在什么地方，每次都是从头开始重新计算的

例如：要计算 tuzi(4)，
>>>> 需要先计算 tuzi(3) 和 tuzi(2)，分解为：
>>>>>>>> 计算 tuzi(3)：需要先计算 tuzi(2) 和 tuzi(1)
>>>>>>>>>> 计算 tuzi(2)：需要先计算 tuzi(1) 和 tuzi(0)
>>>>>>>>>>>> 计算 tuzi(1) 得 1
>>>>>>>>>>>> 计算 tuzi(0) 得 1
>>>>>>>>>> 计算 tuzi(1) 得 1
>>>>>>>> 计算 tuzi(2)：需要先计算 tuzi(1) 和 tuzi(0)
>>>>>>>>>> 计算 tuzi(1) 得 1
>>>>>>>>>> 计算 tuzi(0) 得 1

注意上面每一步计算都是独立的（因为之前的结果并没有保存起来供以后使用），比如 tuzi(2) 就分别计算了两次。

然后，比如 testtuzi 的循环里面，下一步假如开始要计算 tuzi(5)，需要计算 tuzi(4) 和 tuzi(3)，然后虽然上次循环里面 tuzi(4) 和 tuzi(3) 其实已经都算过了，但是不行，这一次里面还是得重新从头开始算。

@kuye 的方法是拿空间换时间的方法（如果我对 PHP 的 static 没理解错的话），拿很少的空间（那个 static array）保存了每次 tuzi($x) 计算的结果，大大提高了后面计算的速度。

[kennedy32]

@dorentus 非常感谢，最详细的解答

[kennedy32]

@kuye 改动最小的方案，谢谢。其实这是MIT600SC第六课递归的例子，能用递归当然最好了

[vibbow]

能30s跑完这个代码的电脑都是神级的电脑了...
我的电脑还在慢慢跑，我看多久能跑完...

[pljhonglu]

其实 LZ 是来秀电脑配置的。。。

[hourui]

楼上正解...

[kofj]

@levn 怎么插入github的这种格式化了的代码的？

[faceair]

@kofj 贴到gist.github.com

[kurtis]

@dorentus
看到现在，只有你got point

这个问题，本质就是应该拿空间换时间。
有张表记录下每次计算的结果作为缓存，以后不用每次计算就可以了。

这个是大学作业吗？好像很久很久以前有人讨论过这个问题了，

[TheJuli]

用超算平台跑一遍试试