主题：很多人说用递归法算斐波那契数效率低，我不信！
ggggqqqqihc [专家分：540] 发布于 2008-02-12 16:37:00
就是很常见的fib(1)=1, fib(2)=1, fib(n)=fib(n-1)+fib(n-2)
我当然不是按着一般的书上写的。
[code=c]
#include <stdio.h>
int fib(int n, int a, int b, int count){
if (count==n){
return b;
}
return fib(n, b, a+b, count+1);
}
int main(){
int n;
scanf("%d",&n);
int s=fib(n,0,1,1);/* 计算第n项 */
printf("%d\n",s);
return 0;
}
[/code]
而一般书上是这样写的：
[code=c]
int fib(int n){
if (n==1||n==2)
return 1;
else
return fib(n-1)+fib(n-2);
}
[/code]
最后更新于：2008-02-12 16:54:00
回复列表 （共37个回复）
21 楼
justforfun626 [专家分：18460] 发布于 2008-02-13 14:49:00
To SonicLing
Where did I need max(n)?
Will you please shut-up your garbage???
Thanks!
PS. I will stop arguing on this thread, it is just wasting my time to argue with people who know-nothing but pretend knowing everything...
I quit!
22 楼
rickone [专家分：15390] 发布于 2008-02-13 14:56:00
我试过了，你满意了
n=1000000，就可以把内存吃得卡不动了，1分多钟没有反应；这不是语言的问题。
23 楼
SonicLing [专家分：6260] 发布于 2008-02-13 14:59:00
[quote]To SonicLing
Where did I need max(n)?
Will you please shut-up your garbage???
Thanks!
PS. I will stop arguing on this thread, it is just wasting my time to argue with people who know-nothing but pretend knowing everything...
I quit!
[/quote]
garbage??? 你真的认为ruby解释器可以把地球都包进去吗？就算能，还有整个宇宙呢。
24 楼
justforfun626 [专家分：18460] 发布于 2008-02-13 15:05:00
[quote]我试过了，你满意了
n=1000000，就可以把内存吃得卡不动了，1分多钟没有反应；这不是语言的问题。[/quote]
Very good! Thanks a lot!!!!
Yes, of course, that is expectable. That was just an exercise of mine for playing rubyquiz code.
In the real world, we use different method to solve different problem.
Nobody needs to do fib in your job, if you really need, call a math library.
You call math library to solve most existing algorithm problems.
[b]What we really need is to solve real world problem which has not been on the textbook or PHD disertation yet. That is where the money is.[/b]
25 楼
SonicLing [专家分：6260] 发布于 2008-02-13 15:13:00
没什么。F数列大数计算使用矩阵法，O(logn)的时间复杂度，O(1)的空间复杂度，算是比较可以接受了。
实在是天文数字，就对n进行划分，然后并行计算。
与ruby无关。
26 楼
rickone [专家分：15390] 发布于 2008-02-13 15:22:00
这下真相大白了。
27 楼
SonicLing [专家分：6260] 发布于 2008-02-13 15:27:00
[quote]
Nobody needs to do fib in your job, if you really need, call a math library.
[/quote]
总算说了句实话。
这个帖子就是讨论效率问题。没人说你的代码garbage，也没人说ruby garbage，也没人敢说你garbage。不要遇到一丁点问题就garbage garbage乱叫。难道跟你意见不一致的都叫garbage？你一开始就把你的对手定位为garbage，那还用讨论个啥？我们这些所谓的“garbage”都来听你讲课好了，你说是1就是1，是2就是2，没啥好讨论了。
28 楼
SonicLing [专家分：6260] 发布于 2008-02-13 15:40:00
本人不喜欢Java、C#，就是因为他们的东西都是不需要讨论的，不可能被misinterpreted，是这样就使这样，是那样就是那样。Java、C#区大多都是死气沉沉的，要么就是那些不知道是不是牛人的牛人们照本宣科贴些东西。
在C/C++区讨论就要尊重对手，因为初学的人也能发现深刻的问题。不管你理解的对不对，各种观点拿出来平等的晒一晒，辩一辩，这样对所有参与的人都有好处。恶毒的攻击对谁都没好处。一来，你说服别人的目的没达到，二来，只能激起更大的反抗。
29 楼
MasterRaySoul [专家分：2830] 发布于 2008-02-13 15:49:00
Ruby 没用过，对它的语法什么的就不敢评论
有没有人注意到我在１０楼所回复的？再贴一遍
分成两个接近的数（差１），近似于二分计算
[code=c]
#include <stdio.h>
unsigned long long fib[200]={0, 1, 1};
unsigned long long Fibonacci(unsigned n)
{
unsigned a, b;
if (fib[n]) return fib[n];
b = (a=n>>1) + (n&1);
return fib[n]=Fibonacci(a)*Fibonacci(b-1) + Fibonacci(a+1)*Fibonacci(b);
}
int main(void)
{
unsigned n;
scanf("%u", &n);
printf("%llu\n", Fibonacci(n));
return 0;
}
[/code]
30 楼
SonicLing [专家分：6260] 发布于 2008-02-13 16:01:00
生成数组的复杂度O(logn)，平均复杂度O(1)，空间复杂度O(max(n))
空间换时间一般要准备N的上限的空间，所以空间复杂度是O(max(n))
如果采用动态大小的空间，该算法的空间复杂度可以降低为O(logn)，但是时间复杂度就不再是O(1)，而是动态空间的维护算法复杂度+O(1)
fun采用了Ruby的动态性，如果考虑这一点的话，空间复杂度是O(n)，但是时间复杂度会相应增加，如同楼主在前面所指出。（PS：这算是对Where did I need max(n)?的回答。）
我来回复
您所在位置：