快速幂

[TieMuZhen]

快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以O(log n)的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。

让我们先来思考一个问题：7的10次方，怎样算比较快？

方法1： 最朴素的想法，77=49，497=343，... 一步一步算，共进行了9次乘法。

这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。

方法2： 先算7的5次方，即77777，再算它的平方，共进行了5次乘法。

但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。

方法3： 先算77得49，则7的5次方为4949*7，再算它的平方，共进行了4次乘法。

模仿这样的过程，我们得到一个在O(log n)时间内计算出幂的算法，也就是快速幂。

递归快速幂

刚刚我们用到的，无非是一个二分的思路。我们很自然地可以得到一个递归方程：

递归快速幂的思路非常自然，代码也很简单（直接把递归方程翻译成代码即可）：

function qpow(a, n) {
    if(n == 0){
        return 1;
    }else if(n % 2 == 1){
        return qpow(a, n - 1) * a;
    }else {
        let tmp = qpow(a, n/2);
        return tmp * tmp;
    }
}

注意，这个tmp变量是必要的，因为如果不把qpow(a, n/2)记录下来，直接写成qpow(a, n /2)*qpow(a, n /2)，那会计算两次qpow(a, n/2)，整个算法就退化为了 O(n)