我是小小强，这是我的第4篇原创文章，阅读需要大约10分钟。

---

题目

LintCode:斐波纳契数列

描述

查找斐波纳契数列中第 N 个数。
所谓的斐波纳契数列是指：
前2个数是 0 和1 。
第 i 个数是第i-1个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

样例

给定 1，返回0
给定 2，返回1
给定10，返回 34

实现

递归实现

1. java代码

class Solution {
    public int fibonacci(int n) {
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

2. 结果分析
   结果：结果不尽人意，速度非常慢，甚至没有通过 LintCode 的评测。
   分析：这种递归不同于一般的递归，在 n 较大时，两次递归调用中存在大量的重复运算，导致速度非常慢。

非递归实现

1. java代码

class Solution {
    public int fibonacci(int n) {
        if(1==n)
            return 0;
        if(2==n)
            return 1;
        int a=0;
        int b=1;
        int sum=0;
        while(n>2)
        {
            sum=a+b;
            a=b;
            b=sum;
            n--;
        }
        return sum;
    }
}

2. 结果分析
   结果：经测试 C++ 最快可以以 10ms 轻松通过 LintCode 的评测。
   分析：时间复杂度为 o(n) ，空间复杂度为 o(1) ，效果不错。
   细节：使用 while 代替 for 节省了一个 Int(4Byte) 的空间。

其它优化参考

斐波纳契数列实现及优化