[算法]程序员必学：快速幂算法( 二 )
本文插图
不难看出 ， 每次调用时 ， n的规模都减半 ， 所以时间和空间复杂度都是O(logn)
如果你的算法功底还行 ， 那就可以用更专业的方法去分析它的复杂度（没有一定的算法基础 ， 可能会看不懂）
![[算法]程序员必学：快速幂算法](http://ttbs.guangsuss.com/image/5ba555f5d4964bc1e176da4c18171d8b)
- 这其实是典型的应用分治策略的算法
- 假设T(n)是数据规模为n时的时间复杂度 ， 不难得出递推式：T(n) = T(n / 2) + O(1)
- 最后通过主定理（Master Theorem）可以直接得出结论：T(n) = O(logn)
我们以求3 ^ 21为例子 ， 来分析一下非递归的代码应该怎么写 。
首先21的二进制形式是10101
![[算法]程序员必学：快速幂算法](http://ttbs.guangsuss.com/image/8ec567e918b8dd66335398eedfb3cf5e)
本文插图
![[算法]程序员必学：快速幂算法](http://ttbs.guangsuss.com/image/5e4172af571b01a913bed90ae3e5acc1)
本文插图
不难得出以下结论
- 3 ^ n（n为2、4、8、16）都可以由3 ^ 1累乘出来
- 每一个3 ^ n都有对应的二进制位
- 3 ^ 1对应二进制位的值是1 ， 其实是二进制10101的最后1位
- 3 ^ 2对应二进制位的值是0 ， 其实是二进制1010的最后1位
- 3 ^ 4对应二进制位的值是1 ， 其实是二进制101的最后1位
- 3 ^ 8对应二进制位的值是0 ， 其实是二进制10的最后1位
- 3 ^ 16对应二进制位的值是1 ， 其实是二进制1的最后1位
- 如果3 ^ n对应二进制位的值是0 ， 就不用乘进最终结果
- 比如3 ^ (8 * 0)、3 ^ (2 * 0)
- 因为它们最终的值都是3 ^ 0 ， 也就是1
- 如果3 ^ n对应二进制位的值是1 ， 就需要乘进最终结果
- 比如3 ^ (16 * 1)、3 ^ (4 * 1)、3 ^ (1 * 1)
- 利用3 ^ 1 ， 不断累乘出3 ^ n（n为2、4、8、16）
- 每当累乘出一个3 ^ n ， 就查看其对应二进制位的值是1还是0 ， 来决定是否要将它乘进最终结果
int fastPower(int x, int n) {int result = 1;while (n != 0) {if ((n & 1) == 1) {result *= x;}x *= x;n >>= 1;}return result;} 代入3和21 ， fastPower(3, 21)的执行流程如下： ------第1轮while循环-----
- n的二进制是10101（十进制是21）
- x = 3 ^ 1, 其对应二进制位的值是1（n的最后一个二进制位）
- 所以需要执行第5行代码
- 将x乘进最终结果
- result = 3 ^ 1
- x = (3 ^ 1) * (3 ^ 1) = 3 ^ 2
- n右移1位 ， 其二进制变成了1010（对应的十进制是啥？不重要！！！）
- n的二进制是1010
- x = 3 ^ 2, 其对应二进制位的值是0（n的最后一个二进制位）
- 所以不需要执行第5行代码
- 不需要将x乘进最终结果
- result = 3 ^ 1
- x = (3 ^ 2) * (3 ^ 2) = 3 ^ 4
- n右移1位 ， 其二进制变成了101（对应的十进制是啥？不重要！！！）
- n的二进制是101
- x = 3 ^ 4, 其对应二进制位的值是1（n的最后一个二进制位）
- 所以需要执行第5行代码
- 将x乘进最终结果
- result = (3 ^ 1) * (3 ^ 4)
推荐阅读
- 工业互联网@程序员的术与道：术——编程基本功之网络编程
- 小谢娱乐哦引来广大网友狂点赞，直呼炸天，程序员用Java实现扫雷小游戏
- Python爱好者社区漫画 | 程序员逆天改命
- Python爱好者社区| 程序员逆天改命，漫画
- 雷军■程序员辞去互联网工作，跨行去传统上市公司，结果上班第1天就蒙了
- 『程序员』身为京东最大股东的马化腾，却在扶持拼多多？刘强东：“请便！”
- 35岁程序员被电信云、华为和阿里同时录取，看到薪资比较后，酸了
- 程序员▲金山云逆势IPO，雷军身价超100亿美元！
- 阿里巴巴@33岁程序员年薪45万，想辞职去阿里上班，结果阿里年薪让他看懵了
- HyperAI超神经Semantic KITTI 评测榜首，识别可达厘米级别，新算法冲上
