剑指offer(C++)-JZ10：斐波那契数列(时间复杂度O(logn)解法)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

斐波那契数列是一个满足如下条件的数列

数据范围：1≤n≤40

要求：空间复杂度O(1)，时间复杂度O(n) ，本题也有时间复杂度O(logn) 的解法

示例：

输入：

4

返回值：

3

说明：

根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。

解题思路：

本题考察算法-动态规划算法的使用，和青蛙跳台阶一样的解法，但本文不探究那些基础解法，来研究下如何实现时间复杂度为O(logn)的解法。思路如下。

斐波那契数列为：

则有如下公式成立：

当n=2时，有：

不难得出：

则：

当知道n以后，只需要求解元矩阵的n-2次方即可，对矩阵的高幂求解，可运用快速幂算法实现提速。

快速幂算法是将高次幂拆解为多个低次幂的组合，如：

13转换为2进制是1101，即8+4+1，那我们如果求解矩阵的13次方，只需要求一次X，X的平方，X的四次方，X的八次方，然后取X的八次方乘X的四次方乘X即可，这样省下了许多运算过程。时间复杂度为O(logn)，如果用遍历的方法求解矩阵的13次方，就相当于执行了13次操作，这样的复杂度就是O(n)。

测试代码：

class Solution {
public:
    int Fibonacci(int n) {
        // 1和2时为1
        if(n == 1 || n == 2)
            return 1; 
        // 根据斐波那契数列可知，元矩阵如下
        vector<vector<int>> element={{1,1},{1,0}};
        // 元矩阵高幂运算，用快速幂算法求解
        vector<vector<int>> result=Counting(element, n-2);
        return result[0][0]+result[0][1];
    }
 
    // 快速幂算法
    vector<vector<int>> Counting(vector> element,int n){
        // 初始化为单元矩阵
        vector<vector<int>> result={{1,0},{0,1}};
        // 基数矩阵
        vector<vector<int>> base=element;
        // 右移幂数，可快速完成求解
        for(;n!=0;n>>=1)
        {
            // 当前位数为1时，矩阵相乘
            if((n&1)!=0)
            {
                result=MatrixCalculation(result, base);
            }
            // 基数矩阵升级幂数
            base=MatrixCalculation(base, base);
        }
        return result;
    }
 
    // 矩阵求解
    vector<vector<int>> MatrixCalculation(vector> a,vector> b){
        vector<vector<int>> result(a.size(),vector(b[0].size(),0));
        for(int i=0;i<a.size();++i)
        {
            for(int j=0;j<b[0].size();++j)
            {
                for(int k=0;k<a[0].size();++k)
                {
                    result[i][j]+=a[i][k]*b[k][j];
                }
            }
        }
        return result;
    }
 
};

用什么容器都可以，原理懂了，实现方法有很多种~