 |
1
递归，循环太多，循环套递归，递归套循环。能不慢么。
|
 |
2
远大于2的60次方次计算，30S就能出结果？不会吧。
能出结果已经很不错了。 |
 |
skyangel3Dec 25, 2013 via iPhone
3
60的fibonnaci sequence 运算30s 在php可以出结果。你的机器已经很牛了
|
 |
5
你用的这个算法是算法导论上用来做反面教材的。
|
 |
justfinduDec 25, 2013
6
这递归到死了吧
|
 |
7
|
 |
ccidcce32167Dec 25, 2013
9
建议你用银河或深蓝来跑这个程序
|
 |
luoyou1014Dec 25, 2013
10
@kennedy32
改用循环写菲波纳锲算法 |
|
11
@luoyou1014 可以把一楼的代码改写一下么??
|
 |
13
|
|
14
@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); |
 |
15
|
 |
16
算法概论第一章吧，就在讲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 |
 |
17
return tuzi($x-1)+tuzi($x-2);
这句话让你的代码变成了一个庞大的2叉树。。。n进去就是2的n-1次方！ |
 |
GolevkaDec 25, 2013
18
因为这种二阶线性递归式直接写出来的话复杂度是exponential time的, 如果一定要递归的话可以用memoization. 所以说那些妄想速成码农就应该尽早砍掉重练, 回去撸一撸SICP和lambda calculus就知道踏实了.
ref: http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html |
 |
21
|
 |
flyawayDec 25, 2013
22
斐波拉契数列，递归的方法存在太多的overlapping，大量重复计算，降低了效率
|
|
26
@luoyou1014 谢谢
|
 |
baiyunheituDec 25, 2013
27
递归的复杂度不太乐观。
|
 |
c742435Dec 25, 2013
28
你用一个数组存储计算结果就可以了。算法不用改。
|
 |
29
一种很肤浅的作法：
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); |
 |
kevinrootDec 25, 2013
30
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 |
 |
31
回答楼主的问题：
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) 计算的结果，大大提高了后面计算的速度。 |
 |
vibbowDec 25, 2013
34
能30s跑完这个代码的电脑都是神级的电脑了...
我的电脑还在慢慢跑，我看多久能跑完... |
 |
pljhongluDec 25, 2013
35
其实 LZ 是来秀电脑配置的。。。
|
 |
houruiDec 25, 2013
36
楼上正解...
|
 |
faceairDec 25, 2013
38
|
 |
kurtisDec 25, 2013
39
@dorentus
看到现在，只有你got point 这个问题，本质就是应该拿空间换时间。 有张表记录下每次计算的结果作为缓存，以后不用每次计算就可以了。 这个是大学作业吗？好像很久很久以前有人讨论过这个问题了， |
 |
TheJuliDec 25, 2013
40
用超算平台跑一遍试试
|
 |
tonicDec 25, 2013
41
可以改成尾递归的... 或者直接改迭代
|
 |
huafangJan 14, 2014
46
你函数还没定义好，就内部调用。。。
|
1
Select Language