2.裴波那契(Fibonacci)数列

裴波那契(Fibonacci)数列

f(n)=

⎧⎩⎨0,1,f(n−1)+f(n−2),n =0n =1n>1

求裴波那契数列的第n项。(题目来自剑指offer)

1.递归解法,效率很低的解法,不用

一看到这个题,我们就很容易窃喜的想到这种解法

很多f(i)进行了重复计算,随着n的增大,计算量急剧增加,时间复杂度以n的指数方式递增,存在很严重的效率问题。

int Fibonacci(int n) {
if(n<=0) return 0;
if(n==1) return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}

2.用循环实现递归,面试官期待的解法(O(n))

方法1中的递归代码之所以慢是因为重复计算的太多,我们只要想办法避免重复就行了。可以把已经得到的数列中间项保存起来,如果下次需要的时候先查找一下,如果前面已经计算过了就不用再重复计算了。

int Fibonacci(int n) {
if(n<=0) return 0;
if(n==1) return 1;
int a=1;
int b=0;
int fib=0;
for(int i=2;i<=n;i++)
{
fib=a+b;
b=a;
a=fib;
}
return fib;
}
上一篇:make,makefile,cmake“暴力编译法”的个人经验或理解。


下一篇:python实现斐波那契查找