Chapter4 Math

快速幂

快速幂是把计算幂次运算需要用 $O(n)$ 的时间复杂度降低到 $O(\log n)$ 的时间复杂度，可以用如下原理解释。

假设我们要计算 $2^{11}$，如果使用暴力求解需要遍历 11 次循环，但我们可以转化成这样理解：

$$2^{11}=2^8\times 2^2\times 2^1 = 2^{2^3}\times 2^{2^1}\times 2^{2^0}$$

不难发现分解之后的指数其实就是用二进制来表示 11 这个数，用二进制表示为 $1101$，正好是对应有 1 的位数，然后乘以前面相应的权重就能得到结果。所以每次计算只需要从右往左找 1，只要找到 1 就乘以对应这个位数转化成十进制的权重 （$2^n$，$n$ 表示位数）。再求其 2 的幂次即可。（在本例中可以理解为在求解 11 的二进制的 2 次幂）