快速幂:实现与数学解释

快速幂(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;
}

该算法的时间复杂度为O(N)。

从数学推导

数学公式：

$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;
    }

当y < 0时，上述代码存在问题。

则修改为：

public double pow(double x, int y) {
        double result = 1.0;
        if(y < 0) {
            x = 1 / x;
            y = -y;
        }
        while(y > 0) {
            if((y & 1) == 1) {
                result *= x;
            }
            x *= x;
            y >>= 1;
        }
        return result;
    }