为什么这段代码的执行时间会超过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);

[Rojey]

递归，循环太多，循环套递归，递归套循环。能不慢么。

[casparchen]

远大于2的60次方次计算，30S就能出结果？不会吧。
能出结果已经很不错了。

[skyangel3]

60的fibonnaci sequence 运算30s 在php可以出结果。你的机器已经很牛了

[goodan]

@skyangel3 是飞播纳妾数列咩…

[wizardoz]

你用的这个算法是算法导论上用来做反面教材的。

[justfindu]

这递归到死了吧

[kennedy32]

@Rojey
@casparchen
@skyangel3

虚拟主机跑到35行，自己的电脑还没试过。我以为是个小运算，很简单的加法。

[kennedy32]

@wizardoz 正确的是怎样？

[ccidcce32167]

建议你用银河或深蓝来跑这个程序

[luoyou1014]

@kennedy32
改用循环写菲波纳锲算法

[kennedy32]

@luoyou1014 可以把一楼的代码改写一下么??

[zencoding]

@kennedy32 这个是一个经典的死递归，从代码层次改变不了多少效率的

[Keita1314]

@kennedy32 用数组别用递归
*a= 1;
*(a+1) =1;
for(int i =2;i<=n;i++)
*(a+i) = *(a+i-1)+*(a+i-2);

[luoyou1014]

@kennedy32

<?php
function tuzi($x){
$sum = 0;
$first=0;
$second=1;
for($i=0;$i<$x;$i++){
$sum = $first + $second;
$first = $second;
$second = $sum;
}
return $sum;
}

function testtuzi($n){
for ($i=0;$i<=$n;$i++){
echo "兔子在".$i."月的数目是".tuzi($i)."<br/>";
}
}
testtuzi(60);

[levn]

http://gist.github.com/mtdowling/4516558

[TMBest]

算法概论第一章吧，就在讲fib的各种算法，更快的算法是用矩阵。最快的是这货：
long int fib(unsigned long int n) {
return lround((pow(0.5 + 0.5 * sqrt(5.0), n) -
pow(0.5 - 0.5 * sqrt(5.0), n)) /
sqrt(5.0));
}
参考：http://www.evanmiller.org/mathematical-hacker.html#HN_Repost

[tonitech]

return tuzi($x-1)+tuzi($x-2);
这句话让你的代码变成了一个庞大的2叉树。。。n进去就是2的n-1次方！

[Golevka]

因为这种二阶线性递归式直接写出来的话复杂度是exponential time的, 如果一定要递归的话可以用memoization. 所以说那些妄想速成码农就应该尽早砍掉重练, 回去撸一撸SICP和lambda calculus就知道踏实了.

ref: http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html

[moondark]

@TMBest 这货也只是理论上的最快，前提是sqrt与pow函数的运行时间较短

[clippit]

@TMBest 这个是直接套通项公式了吧？

[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]

用超算平台跑一遍试试

[tonic]

可以改成尾递归的... 或者直接改迭代

[kennedy32]

@vibbow
@pljhonglu
@hourui

E3 1230 v2 30s跑到36行

[vibbow]

@kennedy32 你怎么做到那么快的？
我 i7-4930mx 跑到 testtuzi(36); 花了332秒...

[wizardoz]

@kennedy32 正确的应该是从底向上，从n = 1 累加到n = x。所以问题不在于用了递归调用，而是在于选了一种有很多冗余计算的算法。

[kennedy32]

@vibbow 我还觉得慢呢，虚拟主机都能跑35

[huafang]

你函数还没定义好，就内部调用。。。