快速幂

介绍

快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 O($\log n$) 的时间内计算 $a^n$ 的小技巧，而暴力的计算需要 O($n$) 的时间。

计算 a 的 n 次方表示将 n 个 a 乘在一起：
$a^{n} = \underbrace{a \times a \cdots \times a}_{n\text{ 个 a}}$。然而当 a,n 太大的时侯，这种方法就不太适用了。不过我们知道：$a^{b+c} = a^b \cdot a^c,\,\,a^{2b} = a^b \cdot a^b = (a^b)^2$。二进制取幂的想法是，我们将取幂的任务按照指数的二进制表示来分割成更小的任务。

算法示例

long long int quik_power(int base, int power)
{
    long long int result = 1;   //用于存储项累乘与返回最终结果，由于要存储累乘所以要初始化为1
    while (power > 0)           //指数大于0说明指数的二进制位并没有被左移舍弃完毕
    {
        if (power & 1)          //指数的当前计算二进制位也就是最末尾的位是非零位也就是1的时候
                                //例如1001的当前计算位就是1， 100*1* 星号中的1就是当前计算使用的位
            result *= base;     //累乘当前项并存储
        base *= base;           //计算下一个项，例如当前是n^2的话计算下一项n^2的值
                                //n^4 = n^2 * n^2;
        power >>= 1;            //指数位右移，为下一次运算做准备
                                //一次的右移将舍弃一个位例如1011(2)一次左移后变成101(2)
    }
    return result;              //返回最终结果
}

---

算法分析

1. 时间复杂度 $O(\log n)$
2. 空间复杂度 $O(1)$