题解 | #斐波那契数列#

算法流程：

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)：使用常数级额外空间

算法思想二：递归

解题思路：

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)。使用矩阵快速幂的方法可以降低时间复杂度。

首先可以构建这样一个递推关系：

                                                

因此：

                                                  

令：

                                                                            

因此只要我们能快速计算矩阵 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