题解 | #斐波那契数列#

#include <vector>
class Solution {
public:
    int Fibonacci(int n) {
        vector<vector<int>> matrix = {{1,1},{1,0}};
        return matrix_power(matrix, n)[0][1];
    }
    vector<vector<int>> matrix_multi(vector<vector<int>> x,vector<vector<int>> y){
        vector<vector<int>> matrix(x.size(), vector<int>(y[0].size()));
        for(int i = 0;i<x.size();i++)
            for(int j = 0;j<y[0].size();j++)
                for(int k=0;k<y.size();k++)
                    matrix[i][j]+=x[i][k]*y[k][j];
        return matrix;     
    }
    vector<vector<int>> matrix_power(vector<vector<int>> m, int n){
        vector<vector<int>> matrix(m.size(), vector<int>(m.size()));
        if(n == 0){
            for(int i=0;i<m.size();i++)
                matrix[i][i] = 1;
            return matrix;
        }
        if(n == 1){
            return m;
        }
        matrix = matrix_power(m, n/2);
        if(n&1){
            return matrix_multi(m, matrix_multi(matrix,matrix));
        }else{
            return matrix_multi(matrix,matrix);
        }
    }
};

目前已知的最优时间复杂度为 O(log n)。其中一个基于矩阵乘法的算法可以实现这一目标。

具体来说，我们可以使用以下矩阵表示斐波那契数列的递推式：

| 1 1 |
| 1 0 |

可以证明，对于任意正整数 n，都有以下公式成立：

| F(n+1) F(n)   | = | 1 1 | ^ n
| F(n)   F(n-1) |   | 1 0 |