509. Fibonacci Number.md

509. Fibonacci Number

思路

求斐波那契数列。

思路一

常用思路就是按照定义迭代计算，很简单，见代码。

时间复杂度O(N)，空间复杂度O(1)。

思路二

除了基本的思路，还有个O(logN)复杂度求斐波那契数列的思路。

根据定义，我们有

| F(N)   F(N-1)|   | 1  1 |(N-1)
|              | = |      |
| F(N-1) F(N-2)|   | 1  0 |

以上公式不难用归纳法证明。所以要想得到F(N)，只需要求得矩阵

|1 1|
|1 0|

的N-1次方。如何求这个矩阵的乘方呢，如果简单地循环N-1次那么复杂度还是O(N)。而我们知道求乘方有一个O(logN)的二分算法：

• n为偶数：A^n = A^(n/2) * A^(n/2)
• n为奇数：A^n = A^(n/2) * A^(n/2) * A

以上求乘方的方法可以很方便地用递归实现。

这种思路虽然时间复杂度为O(logN)，但是隐含的时间常数比较大，所以不是很常用，这里代码略。但是这种用O(logN)的二分求乘方的思路是值得我们学习的。

C++

思路一

class Solution {
public:
    int fib(int N) {
        if(N <= 1) return N;
        int pre = 1, prepre = 0, tmp;
        for(int i = 2; i <= N; i++){
            tmp = pre + prepre;
            prepre = pre;
            pre = tmp;
        }
        return pre;
    }
};