算法思想一：迭代

解题思路：

算法流程：
1、当 n < 2时，直接返回 n
2、设置两个变量 one = 1, two = 0
3、循环
    1、计算前两个数字之和 FN
    2、将前两个数字更新  two = one; one = FN
4、循环结束返回最终结果 FN
图解：

代码展示：

Python版本 
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n < 2:
            return n
        one = 1
        two = 0
        for i in range(2, n+1):
            fN = one + two
            two = one
            one = fN
        return fN

复杂度分析

时间复杂度O(N)：迭代n次
空间复杂度O(1)：使用常数级额外空间

算法思想二：递归

解题思路：

算法流程：
1、当 n < 2时，直接返回 n
2、递归算法：Fibonacci(n-1) + Fibonacci(n-2);

代码展示：

JAVA版本
public class Solution {
    public int Fibonacci(int n) {
        if (n < 2){
            return n;
        }
        
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}

复杂度分析

时间复杂度O(N)：递归n次
空间复杂度O(N)：递归栈使用空间

算法思想三：矩阵快速幂

解题思路：

方法一的时间复杂度是 O(n)。使用矩阵快速幂的方法可以降低时间复杂度。
首先可以构建这样一个递推关系：
                                                
因此：
                                                  
令：
                                                                            
因此只要我们能快速计算矩阵 M 的 n 次幂，就可以得到 F(n) 的值。如果直接求取 M^n，时间复杂度是 O(n)，可以定义矩阵乘法，然后用快速幂算法来加速这里 M^n的求取

代码展示：

Python版本 
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n < 2:
            return n
        
        q = [[1, 1], [1, 0]]
        res = self.matrix_pow(q, n - 1)
        return res[0][0]
    def matrix_pow(self, a, n):
        ret = [[1, 0], [0, 1]]
        while n > 0:
            if n & 1:
                ret = self.matrix_multiply(ret, a)
            n >>= 1
            a = self.matrix_multiply(a, a)
        return ret

    def matrix_multiply(self, a, b):
        c = [[0, 0], [0, 0]]
        for i in range(2):
            for j in range(2):
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
        return c

复杂度分析

时间复杂度O(logn)
空间复杂度O(1)