很多人说用递归法算斐波那契数效率低，我不信！

主题：很多人说用递归法算斐波那契数效率低，我不信！

[所有回帖] [只看作者帖] [只看得分帖]

作者：ggggqqqqihc

专家分：540

级别:3

会员信息

发短消息

所属博客

发表时间：2008-2-12 16:37:00 [回复]

楼主

就是很常见的fib(1)=1, fib(2)=1, fib(n)=fib(n-1)+fib(n-2)
我当然不是按着一般的书上写的。

#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;
}

而一般书上是这样写的：

int fib(int n){
  if (n==1||n==2)
    return 1;
  else
    return fib(n-1)+fib(n-2);
}

最后修改于2008-2-12 16:54:00

我的Blog

Python好，Python妙，Python代码呱呱叫。

0

我要推荐

作者：x2222wm

专家分：150

级别:1

会员信息

发短消息

所属博客

发表时间：2008-2-12 16:50:00 [回复] [引用]

1楼

请问，你是和什么样的比确定它的效率高的？

作者：SonicLing

专家分：6260

级别:32

会员信息

发短消息

所属博客

发表时间：2008-2-12 17:24:00 [回复] [引用]

2楼

将你的算法改为循环更快。

作者：雨中飞燕

专家分：18980

级别:95

会员信息

发短消息

所属博客

发表时间：2008-2-12 17:27:00 [回复] [引用]

3楼

你这样写效率还是低 O(n)
教材代码是 O(n^2)
实用的算法应该是 O(logn)

作者：bpttc

专家分：8790

级别:44

会员信息

发短消息

所属博客

发表时间：2008-2-12 18:03:00 [回复] [引用]

4楼

呵呵裁枝了嘛
最实用的算法应该是o(1)哈哈直接套公式

作者：ggggqqqqihc

专家分：540

级别:3

会员信息

发短消息

所属博客

发表时间：2008-2-12 18:46:00 [回复] [引用]

5楼

引用：
你这样写效率还是低 O(n)
教材代码是 O(n^2)
实用的算法应该是 O(logn)

教材的递归写法的复杂度是
$http://www.forkosh.dreamhost.com/mathtex.cgi?O((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)$
这可比O(n^2)大多了。

我还真不知道O(logn)的方法，透露一下？

作者：bpttc

专家分：8790

级别:44

会员信息

发短消息

所属博客

发表时间：2008-2-12 19:07:00 [回复] [引用]

6楼

引用：
引用：
你这样写效率还是低 O(n)
教材代码是 O(n^2)
实用的算法应该是 O(logn)

教材的递归写法的复杂度是
$http://www.forkosh.dreamhost.com/mathtex.cgi?O((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)$
这可比O(n^2)大多了。

我还真不知道O(logn)的方法，透露一下？

这个怎么看上去像是F数列的通项呢？？

转换成矩阵乘法就是 o( logn ) 啦

lz可以试试将F数列的定义式改写成矩阵乘法

作者：justforfun626

专家分：18430

级别:93

会员信息

发短消息

所属博客

发表时间：2008-2-13 2:58:00 [回复] [引用]

7楼

My Ruby code:

fib = Hash.new{ |h, n|
  if n < 2
    h[n] = n
  else
   m = 2
   while n>=m
    h[m] = h[m-2] + h[m-1]
    m += 1
   end
   h[n]
  end
}

puts fib[10000]
==================
result:
3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551363373402
5582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652
7313000888302692356736131351175792974378544137521305205043477016022647583189065278908551543661595829
8727968298751063120057542878345321551510387081829896979161312785626503319548714021428753269818796204
6936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046
0889239623288354615057765832712525460935911282039252853934346209042452489294039017062338889910858410
6518317336043747073790855263176432573399371287193758774689747992630583706574283016163740896917842637
8624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883
8319233867830561364353518921332797329081337326426526339897639227234078829281779535805709936910491754
7080893184105614632233821746563732124822638309210329770164805472624384237486241145309381220656491403
2751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345
5573667197313927462736291082106792807847180353291311767789246590899386354593278945237776744061922403
3763867400402133034329749690202832814593341882681768389307200363479562311710310129195316979460763273
7589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034
6149322911059706762432685159928347098912847067408620085871350162603120719031720860940812983215810772
8207635318662461127824553720853236530577595643007251774431505153960090516860322034916322264088524885
2433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052
4025327097469953187707243768259074199396322659841474981936092852239450397071654431564213281576889080
5878318340491743455627052022356484649519611246026831397097506938264870661326450766507461151267752274
8621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133
252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

It is O(n), however, all fibonacci number from 1-10000 are stored, if you want fib[9000] now, it takes no time at all.

作者：justforfun626

专家分：18430

级别:93

会员信息

发短消息

所属博客

发表时间：2008-2-13 9:36:00 [回复] [引用]

8楼

After posting above code, I realized, there is a problem with above code.

After calculate fib[10000], if I need to calculate fib[11000]., it will start over, recalculate everything.

I have put an improved version on my website now, read there if you are interested.

http://bobcat.webappcabaret.net/javachina/faq/ruby_01.htm#ruby_Q015

作者：ggggqqqqihc

专家分：540

级别:3

会员信息

发短消息

所属博客

发表时间：2008-2-13 11:31:00 [回复] [引用]

9楼

to justforfun626:

I don't think you are right, because of Hash. You don't know the hash function and how Ruby store all the numbers in the memory. It is inexact to say "it is O(n)".

I don't think high level language is proper for algorithm analysis, although I like them very much.

最后修改于2008-2-13 11:36:00

作者：MasterRaySoul

专家分：2830

级别:15

会员信息

发短消息

所属博客

发表时间：2008-2-13 12:22:00 [回复] [引用]

10楼

#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;
}

作者：justforfun626

专家分：18430

级别:93

会员信息

发短消息

所属博客

发表时间：2008-2-13 12:51:00 [回复] [引用]

11楼

引用：
to justforfun626:

I don't think you are right, because of Hash. You don't know the hash function and how Ruby store all the numbers in the memory. It is inexact to say "it is O(n)".

I don't think high level language is proper for algorithm analysis, although I like them very much.

To ggggqqqqihc
Haha, have you tried it, tested it???

What you think or think not does not matter at all, the important thing is what is the fact!!!

If you don't know what you are talking about, please stop talking and start to learn!!!

Thanks!

最后修改于2008-2-13 14:03:00

作者：SonicLing

专家分：6260

级别:32

会员信息

发短消息

所属博客

发表时间：2008-2-13 13:38:00 [回复] [引用]

12楼

fun大概想说明这个意思:

int fibonacci(int n)
{
    static int fib[MAX] = {0}; // 假设int不会溢出
    static int max_n = 0;
    assert(n < MAX);
    while(n > max_n && max_n < MAX)
    {
        max_n++;
        if(max_n <= 2) fib[max_n] = 1;
        else fib[max_n] = fib[max_n-1] + fib[max_n-2];
    }
    return fib[min(n, MAX-1)];
}

这个时间复杂度应该是O(1)，空间复杂度是无穷大。（理论上来说）

用空间换时间。一般来说，规模有上限的前提下可以这么做。

不过在规模没有上限的前提下，这个方法不可靠，因为不可能有无穷大的空间供你支配。

最后修改于2008-2-13 13:45:00

作者：MasterRaySoul

专家分：2830

级别:15

会员信息

发短消息

所属博客

发表时间：2008-2-13 13:54:00 [回复] [引用]

13楼

引用：
fun大概想说明这个意思:

int fibonacci(int n)
{
    static int fib[MAX] = {0}; // 假设int不会溢出
    static int max_n = 0;
    assert(n < MAX);
    while(n > max_n && max_n < MAX)
    {
        max_n++;
        if(max_n <= 2) fib[max_n] = 1;
        else fib[max_n] = fib[max_n-1] + fib[max_n-2];
    }
    return fib[min(n, MAX-1)];
}

这个时间复杂度应该是O(1)，空间复杂度是无穷大。（理论上来说）

用空间换时间。一般来说，规模有上限的前提下可以这么做。

不过在规模没有上限的前提下，这个方法不可靠，因为不可能有无穷大的空间供你支配。

这不是输出数列吗？不用数组，两个变量相互做加法、输出不是更好？

作者：justforfun626

专家分：18430

级别:93

会员信息

发短消息

所属博客

发表时间：2008-2-13 13:59:00 [回复] [引用]

14楼

Can you all stop misinterpreting what I mean, please???

If you don't know what you are talking about, please stop talking and start to learn!!!

Thanks!

最后修改于2008-2-13 14:06:00

作者：rickone

专家分：15390

级别:77

会员信息

发短消息

所属博客

发表时间：2008-2-13 14:11:00 [回复] [引用]

15楼

fun已经说了他的程序是O(n)的,但是算了n=10000之后,再算n<10000的数,就几乎不要时间,因为前面的数都存在'Hash'表里面,你只需要读出来,如果你还想算n>10000的斐数,他有一个更好的程序在他的个人主页里,请去参考一下.
而后面一位朋友是说,他认为Ruby是高级语言,你不知道那个Hash是如何实现的,所以不能说是O(n)
我也不太了解Ruby，所以我不敢评论，但是O(n)的O(logn)是相差很多的，算斐数算是很轻松的事情对于很多C/C++大数库来说，不要说n=10000，就算是阶乘也算不上什么鸡毛蒜皮的事，如果O(n)的算法算10,000要1s，那算10,000,000至少要大1000倍，还不考虑你的大数基本运算的时间开销，而O(logn)的算法可能只需要2s，只是一个感性比较。

作者：justforfun626

专家分：18430

级别:93

会员信息

发短消息

所属博客

发表时间：2008-2-13 14:17:00 [回复] [引用]

16楼

Test my code is very simple.

1) Download ruby, install it, make sure downloading the correct one for your OS
2) Append your ruby_dir/bin to your path/PATH
3) Copy and save my code as fib.rb or whatever.rb
4) Open a cmd/console window or unix terminal in the directory contain the file
5) type ruby fib.rb
6) You got the result

You don't need to understand ruby syntax to test my code.

最后修改于2008-2-13 14:25:00

作者：ggggqqqqihc

专家分：540

级别:3

会员信息

发短消息

所属博客

发表时间：2008-2-13 14:37:00 [回复] [引用]

17楼

to justforfun626:

虽然我没有用Ruby做过项目，但你的代码我想我还是能明白的。
虽然hash table是一个近似于O(1)的操作，整体代码的复杂度也的确是O(n)，但高阶的语言掩盖了算法的复杂度。假如你用一种tree map数据结构，那复杂度就会接近O(nlogn)，但体现在代码中的复杂度看起来还是O(n)——如果你不知道内部采用的数据结构的话。

好比有些人写一个将小写字母变成大写的代码：

for (int i=0;i<strlen(s);++i){
s[i]=toupper(s[i]);
}

看起来是O(n)，实际上是O(n^2)（因为C语言的strlen复杂度是O(n)）。

当然你的代码是很快的，就算是算10000000项也很快，但算法分析不是测量运行时间。

最后修改于2008-2-13 14:50:00

作者：SonicLing

专家分：6260

级别:32

会员信息

发短消息

所属博客

发表时间：2008-2-13 14:38:00 [回复] [引用]

18楼

引用：
fun已经说了他的程序是O(n)的,但是算了n=10000之后,再算n<10000的数,就几乎不要时间,因为前面的数都存在'Hash'表里面,你只需要读出来,如果你还想算n>10000的斐数,他有一个更好的程序在他的个人主页里,请去参考一下.
而后面一位朋友是说,他认为Ruby是高级语言,你不知道那个Hash是如何实现的,所以不能说是O(n)
我也不太了解Ruby，所以我不敢评论，但是O(n)的O(logn)是相差很多的，算斐数算是很轻松的事情对于很多C/C++大数库来说，不要说n=10000，就算是阶乘也算不上什么鸡毛蒜皮的事，如果O(n)的算法算10,000要1s，那算10,000,000至少要大1000倍，还不考虑你的大数基本运算的时间开销，而O(logn)的算法可能只需要2s，只是一个感性比较。

他的改进算法没看很明白，但是所谓改进，无非就是不再重复计算已经计算过的数，或者尽量减少重复计算。时间换空间的本质没有改变，空间复杂度O(max(n)/200)和O(max(n))都将趋向无穷大，没有本质的区别。

F数列的矩阵算法看了一下，大概就是让x=(1,0)重复乘以一个2*2的矩阵因子A：
1 1
1 0
最后(fn, fn-1) = x * A^n

而A的n次幂可以用反复平方法获得O(logn)的低复杂度， x * A^n实际上就是取A^n矩阵的第一行。

作者：justforfun626

专家分：18430

级别:93

会员信息

发短消息

所属博客

发表时间：2008-2-13 14:40:00 [回复] [引用]

19楼

To ggggqqqqihc
Haha, have you tried it, tested it???

What you think or think not does not matter at all, the important thing is what is the fact!!!

If you don't know what you are talking about, please stop talking and start to learn!!!

Thanks!

作者：justforfun626

专家分：18430

级别:93

会员信息

发短消息

所属博客

发表时间：2008-2-13 14:43:00 [回复] [引用]

20楼

for (int i=0;i<strlen(s);++i){
s[i]=toupper(s[i]);
}

Nobody will write such stupid code, except ...

http://www.starstore.com/acatalog/Shrek_2_Donkey_L_poster.jpg

最后修改于2008-2-13 14:44:00