【数据结构与算法】快速幂

快速幂是用来解决求幂运算的高效方式。

例如我们要求 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) \]

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzxxpp.html