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

kennedy32 · 2013-12-24T19:46:31Z

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 "; } } testtuzi(60);

tuzi

testtuzi

return

46 replies • 1970-01-01 08:00:00 +08:00

1

Rojey

Dec 25, 2013

1

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

2

casparchen

Dec 25, 2013

1

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

3

skyangel3

Dec 25, 2013 via iPhone

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

4

goodan

Dec 25, 2013 via iPhone

@skyangel3 是飞播纳妾数列咩…

5

wizardoz

Dec 25, 2013

1

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

6

justfindu

Dec 25, 2013

这递归到死了吧

7

kennedy32

OP

Dec 25, 2013

@Rojey
@casparchen
@skyangel3

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

8

kennedy32

OP

Dec 25, 2013

@wizardoz 正确的是怎样？

9

ccidcce32167

Dec 25, 2013

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

10

luoyou1014

Dec 25, 2013

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

11

kennedy32

OP

Dec 25, 2013

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

12

zencoding

Dec 25, 2013

1

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

13

Keita1314

Dec 25, 2013

1

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

14

luoyou1014

Dec 25, 2013

1

@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

levn

Dec 25, 2013

1

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

16

TMBest

Dec 25, 2013

1

算法概论第一章吧，就在讲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

tonitech

Dec 25, 2013

1

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

18

Golevka

Dec 25, 2013

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

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

19

moondark

Dec 25, 2013

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

20

clippit

Dec 25, 2013

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

21

anheiyouxia

Dec 25, 2013

1

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

22

flyaway

Dec 25, 2013

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

23

skydiver

Dec 25, 2013 via Android

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

24

skydiver

Dec 25, 2013

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

25

kennedy32

OP

Dec 25, 2013

@Keita1314 额，我只看得懂php

26

kennedy32

OP

Dec 25, 2013

@luoyou1014 谢谢

27

baiyunheitu

Dec 25, 2013

递归的复杂度不太乐观。

28

c742435

Dec 25, 2013

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

29

kuye

Dec 25, 2013

1

一种很肤浅的作法：
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);

30

kevinroot

Dec 25, 2013

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

dorentus

Dec 25, 2013

2

回答楼主的问题：

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) 计算的结果，大大提高了后面计算的速度。

32

kennedy32

OP

Dec 25, 2013

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

33

kennedy32

OP

Dec 25, 2013

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

34

vibbow

Dec 25, 2013

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

35

pljhonglu

Dec 25, 2013

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

36

hourui

Dec 25, 2013

楼上正解...

37

kofj

Dec 25, 2013

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

38

faceair

Dec 25, 2013

@kofj 贴到gist.github.com

39

kurtis

Dec 25, 2013

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

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

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

40

TheJuli

Dec 25, 2013

用超算平台跑一遍试试

41

tonic

Dec 25, 2013

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

42

kennedy32

OP

Dec 25, 2013

@vibbow
@pljhonglu
@hourui

E3 1230 v2 30s跑到36行

43

vibbow

Dec 26, 2013

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

44

wizardoz

Dec 26, 2013

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

45

kennedy32

OP

Dec 26, 2013

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

46

huafang

Jan 14, 2014

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