本文参考
LeetCode 50.Pow(x, n)

1.概述

（1）快速幂 (Fast Power)，顾名思义，就是快速算底数 x 的 n 次幂。其核心思想就是每一步都把指数减半，而相应的底数做平方运算。这样不仅能把非常大的指数给快速变小，所需要执行的循环次数也变小，而最后表示的结果不会变化。

（2）快速幂算法的本质是分治算法。例如我们要计算 $x^{64}$ ，我们可以按照：

$x$ → $x^2$ → $x^4$ → $x^8$ → $x^{16}$ → $x^{32}$ → $x^{64}$

的顺序，从 x 开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到 $x^{64}$ 的值，而不需要对 x 乘 63 次 x。而如果我们要计算 $x^{77}$，我们可以按照：

$x$ → $x^2$ → $x^4$ → $x^9$ → $x^{19}$ → $x^{38}$ → $x^{77}$

的顺序，在 $x$ → $x^2$、$x^2$ → $x^4$、$x^{19}$ → $x^{38}$ 这些步骤中，我们直接把上一次的结果进行平方；而在 $x^4$ → $x^9$、$x^9$ → $x^{19}$、$x^{38}$ → $x^{77}$ 这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x。

（3）直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。但如果我们从右往左看，分治的思想就十分明显了：

• 当我们要计算 $x^n$ 时，我们可以先递归地计算出 $y=x^{\lfloor n/2\rfloor }$ ，其中 $\lfloor a\rfloor$ 表示对 a 进行下取整；
• 根据递归计算的结果，如果 n 为偶数，那么 $x^n$ = $y^2$；如果 n 为奇数，那么 $x^n$ = $y^2$ * $x$；
• 递归的边界为 n = 0，任意数的 0 次方均为 1。

（4）由于每次递归都会使得指数减少一半，因此递归的层数为 log₂n，，故其时间复杂度为 O(log₂n)，与朴素的 O(n) 方法（即 n 个底数直接相乘）相比效率有了极大的提高。

2.代码实现

（1）快速幂的递归代码如下，其时间复杂度为 O(log₂n)。

class Solution {

    //求 x 的 n 次幂
    public double myPow(double x, int n) {
        long N = n;
        if (N >= 0) {
            return quickMul(x, N);
        } else {
            return 1.0 / quickMul(x, N);
        }
    }
    
    private double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        if (N % 2 == 0) {
            return y * y;
        } else {
            return y * y * x;
        }
    }
}

（2）快速幂的非递归代码如下，其时间复杂度为 O(log₂n)。

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