为什么这段代码的执行时间会超过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 这个是直接套通项公式了吧？