快速幂是用来解决求幂运算的高效方式。
例如我们要求 x 的 90 次方,一般的方法可以通过一个循环,每次乘一个 x,循环 90 次之后就可以得到答案,时间复杂度为 O(n),效率较低。而通过快速幂,我们可以在 O(log(n)) 的时间复杂度内完成该运算。
具体方法我们可以通过二进制的视角来看待幂运算。
要计算的是 $ \mathrm{x}^{\mathrm{n}} $,把 n 以二进制的形式展开。
\[\mathrm{n}=\,\,\left( ...\mathrm{b}_3\mathrm{b}_2\mathrm{b}_1\mathrm{b}_0 \right) _2\,\,\left( \mathrm{b}_{\mathrm{i}}\text{为}0\text{或}1 \right) \]