分治—快速幂与斐波那契数列

快速幂

letcode—50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

整体考虑，分为两种情况：

1. n为非负整数
2. n为负整数，求出x的-n次方为ans，然后返回1/ans。

暴力解法

double myPow(double x,int n)
{
    double ans=1;
    long long N=n>=0?n:-n;//避免取负号后数据溢出
    for(int i=1;i<=N;i++)
        ans*=x;
    return n>=0?ans:1/ans;
}

快速幂

首先我们考虑n为非负整数，这里可以分为两种情况

1. n为偶数，x^n=(x(n/2))^2；
2. n为奇数，x^n=(x(n/2))^2*x

于是我们可以很清楚的看到，我们把n不断划分，求解更小的解，直到n等于1，这其实就是个递归的过程，最后时间复杂度就从暴力的n降低到了lgn

递归写法

double quickMul(double x, long long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

迭代写法

由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。我们尝试一下会发现，上诉递归的自顶而下似乎解决不了问题，我们尝试自底而上，当然自底向上进行推导是不容易的，因为我们不知道是否需要额外乘 x。但我们不妨找一找规律，看看哪些地方额外乘了 x，并且它们对答案产生了什么影响。

我们拿x^99举例，我们把用递归的思路写出来后再反过来

要是我们从第9步推到第一步很容易，可是从第一步推到第9步就不容易了，我们提供一个非常妙的思路

我们把需要额外加的1做一个标记为+1，初始状态定为0，再+1。

我们假设加的每次次幂需要+1时的乘入的x不同，在例子中，第二，七，九步分别有一个+1，设他们乘入的x为x1，x2，x3（注意他们的值都是相同的），初始状态时的+1定为x0

最后我们可以得到

1. 1->2的时候，x0贡献了2^1个x
2. 2->3的时候，x0贡献了2^1个x，x1贡献了1个x
3. 3->6的时候，x1贡献了2^{2个x，x1贡献了2}1个x
4. 6->48的时候，从第三步到第六步，经过了3步，所以x0贡献了2^{(2+3)个x，x1贡献了2}(1+3)个x
5. 以此类推，x^{99由x0贡献了2}6个x，x1贡献了2^{5个x，x2贡献了2}1个x，x3贡献了一个x

那么上诉有什么规律呢，规律就是99是所有贡献的和，而且贡献可以拆分为2的次幂的和，这直接对应了99的二进制。

99的二进制为……0001100011，于是我们就可以迭代求出n的二进制串中1的位置，最后展开求和

细节看代码

class Solution {
public:
    double quickMul(double x, long long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

看到这，应该就明白了快速幂中的分治思想了，接下来我们来求解一个大家熟悉的问题，斐波那切数列的第n项

斐波那切数列的第n项

这里斐波那切数列从第零项开始，第0项为0，第一项为1，后面为1,2,3,5……

自顶而下

递归暴力写法

这个相信不要多说了

int solution(int n)
{
    if(n==1||n==2)
        return 1;
    return solution(n-1)+solution(n-2);
}

递归优化

我们对上面的递归代码进行分析可以发现，我们似乎重复求了很多东西，比如求第n项时求解了n-1项和第n-2项，但是我们求解n-1的时候又把n-2项求了一遍，也就是说，1到n项大部分都求了两次。

所以我们可以求出来之后，把结果存储起来，后续使用的时候发现已经求过了直接用就行，给出上诉递归的优化代码

int  num[100010]={0,1,1};
int solution(int n)
{
    if(num[n])
        return num[n];
    nums[n]=solution(n-1)+solution(n-2);
    return num[n];
}

这样时间复杂度就直接降到了n，但是递归会使用一定空间，所以我们用迭代写法，和递归的自顶而下不同，迭代是自底向上

自底向上

递归优化转迭代

时间复杂度n

int  num[100010]={0,1,1};
int solution(int n)
{
    for(int i=3;i<=n;i++)
        num[i]=num[i-1]+num[i-2];
    return num[n];
}

矩阵快速幂

时间复杂度n已经很好了，但是前辈们还不满足，研究出了lgn的算法，这里我们直接讲述算法

这个方法就是矩阵快速幂，如图，我们定义两个矩阵

我们发现，两个矩阵相乘会出现下面这个矩阵

且我们发现，原来的第一个矩阵，左上角的1可以代表斐波那切数列第二项，左下角和右上角的1可以代表斐波那契数列第二项，右下角的0可以代表斐波那切数列代表数列第一项

最后我们得到的结论就是，若n为1，直接返回，若n>1，则取第一个矩阵的n-1次幂后得到的矩阵的左上角元素为第n项，然后矩阵的次幂我们采用快速幂思想，最后得到一个lgn的算法

代码实现的细节很多，可以自己尝试写出来，这里留作思考。