剑指offer面试题10:斐波那契数列(Java版)
题目
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第一项为1)。
思路
对于这道题,我们常见是递归法求解,如下
int Fibonacci(int n)
{
if(n==0)
{
return 0;
}
if(n==1)
{
return 1;
}
return Fibonacci(n-1)+Fibonacci(n-2);
}
但是这种解法有很严重的效率问题,举个例子,如果想求解f(10),得先要求得f(9),f(8),同样求解f(9),需要先求得f(8)和f(7)…,求解依赖关系如下
由图可知,有很多重复的值,这意味着一个同样的值需要多次计算,而且计算量会随着n的增大而急剧增加,这就带来了严重的性能问题。综上上述,递归解法主要是重复的计算太多,因此想改进该方法,只需要避免重复计算就行了。
简单的改进方法是从下到上计算,首先根据f(0)f(1)计算出f(2),再根据f(1)f(2)算出f(3)…依次类推就可以算出第n项,时间复杂度为O(n)实现代码如下
int Fibonacci(int n)
{
int []result={0,1};
if(n<2)
{
return result[n];
}
int fibNMinusOne=1;
int fibNMinusTwo=0;
int fibN=0;
for(int i=2;i<=n;i++)
{
fibN=fibNMinusOne+fibNMinusTwo;
fibNMinusTwo=fibNMinusOne;
fibNMinusOne=fibN;
}
return fibN;
}