快速幂

快速幂(Exponentiation by squaring)或者叫平方求幂，是一种求幂函数算法。

它可以以O(logN)的时间复杂度求任意乘方。

引入

如何求8的6次方？

常规算法：

private double pow(double x, int y) {
    double result = 1;
    for (int i = 0; i < y; i++) {
        result *= x;
    }
    return result;
}

实际上，这样的暴力相乘并不高效。

再回想数学公式： $$ a ^ n * a ^ n = a ^ {2n} \ a ^ n * a ^ m = a ^ {n + m} $$ 那我们实际上可以理一下我们的思路，我们要计算 6 次方。

那么实际上可以将式子简化为： $$ 8 ^ 6 = 8 ^ 3 * 8 ^ 3 ;;;① \ 8 ^ 3 = 8 ^ 2 * 8 ^ 1;;;②\ 8 ^ 2 = 8 ^ 1 * 8 ^ 1;;;③ $$ 根据上述理论，可以写出如下方程式： $$ a ^ n = \left{\begin{matrix} a ^ {n - 1},;;;;;;;; n是奇数\ a ^ \frac{n}{2} * a ^ \frac{n}{2},;;;; n是偶数 \ 1,;;;;;;;;;;;n为0 \end{matrix}\right. $$ 翻译为代码则为：

private double pow(double x, int y) {
        if (y == 0) {
            return 1;
        } else if (y % 2 == 1) {
           return pow(x, y - 1) * x; 
        } else {
            double temp = pow(x, y / 1);
            return temp * temp;
        }
    }

其中，利用到了 二分查找 的思想。

递归虽然简洁，但会产生额外的空间开销。将递归改写为循环，来避免对栈空间的大量占用，也就是非递归快速幂。

非递归快速幂

从另一个视角引入快速幂：

如果你的数学基础牢固，那你应该可以很快想到：

任何自然数都可以转化为 2的n次方相乘 这是由二进制表达所决定的。

例如： $$ 2023 = (0111; 1110; 0111)_{2} = 2^0+2^1+2^2+2^5+2^6+2^7+2^8+2^9+2^{10} $$ 二进制上从右往左第n位，分别代表2 的 n - 1次方，而所有的数都可以用二进制表示，所以我们可以根据二进制来优化幂的计算。

也就是说，所有的幂计算都可以看作是底数的2的n次方幂相乘。

例如： $$ 3^{999} = 3^{512}+3^{256}+3^{128}+3^{64}+3^{32}+3^{4}+3^{2}+3^{1} $$ 其中 512、256、128、64、32、4、2和1都是 2 的 n 次方。

将以上理论转化为代码可得：

double pow(double x, int y)
    {
        double result = 1;
        while (y != 0)
        {
            if ((y & 1) == 1) {
                result *= x;
            }
            y >>= 1;      
            x *= x;
        }
        return result;
    }

在每次循环，x 都会成为 x 的平方。

第一次循环是 x 的 2 次方，第二次循环是 x 的 4 次方，以此类推。最终通过上述理论快速计算幂，节省堆栈开销。