[算法学习]斐波那契数计算

算法

问题描述： Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

分析：
这里有两种解法，一种是用递归，一种使用循环。用递归的解法看起来很很简单，只需几行的代码就可以搞定，但是却隐藏着巨大的空间消耗和时间 消耗 。一种使用循环来做，写起来有点难看，至少没递归写起来好看，但是却比递归效率更高，几乎没有内存消耗。

代码思路

（1）. 递归。代码如下（时间复杂度是指数级！大约是(5/3)^N，N很大的时候StackOverflowError，应该是存放递归方法的栈空间溢出）：

1
2
3
4
5
6
7
8
9
10
11
12
public static int getFibonacci(int n)
{
    if(n<1)
    {
        return 0;
    }
    if(n==1||n==2)
    {
        return 1;
    }
    return getFibonacci1(n-1)+getFibonacci1(n-2);
}

（2）. 循环。代码如下（时间复杂度是O(N)）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int getFibonacci(int n)
{
    if(n<1)
    {
        return 0;
    }
    if(n==1||n==2)
    {
        return 1;
    }
    int sum=0;
    int sum1=1;int sum2=1;
    for(int i=3;i<=n;i++)
    {
        sum=sum2+sum1;
        sum1=sum2;
        sum2=sum;
    }
    return sum;
}