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

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

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

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

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

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

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

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

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

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

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

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

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

My Ruby code:
[code=c]
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
[/code]




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.

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.

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

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.

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