江苏龙网

  1. 首页 > 人文 > >

[算法]程序员必学：快速幂算法


关于快速幂 其实快速幂相关的问题 ， 是参加算法竞赛（NOI、ACM等）的小伙伴必须要掌握的一小块基础内容 。 当然 ， 就算你不打算参加算法竞赛 ， 个人觉得只要你是一名程序员 ， 就必须要掌握快速幂算法 。
在《计算机程序设计艺术》一书中就有提到快速幂算法 ， 此书的英文名是The Art of Computer Programming ， 简称TAOCP 。
[算法]程序员必学：快速幂算法
本文插图
Knuth前辈是在计算机领域成就颇丰的知名科学家 ， 是著名的KMP算法的发明人之一 ， 在1974年获得“计算机领域的诺贝尔奖”：图灵奖（当年他才36岁） 。 目前TAOCP已经出版了第1、2、3、4A卷 ， 按照计划 ， 还有第4B、5、6、7卷未出版 。 第一卷首发于1968年 ， Knuth前辈今年是82岁高寿 ， 据说他计划在105岁之前完成这部巨著 。

[算法]程序员必学：快速幂算法
本文插图
关于TAOCP ， 微软创始人Bill Gates曾说过
If you think you're a really good programmer… read (Knuth's) Art of Computer Programming… You should definitely send me a resume if you can read the whole thing.
大概意思是：如果你认为自己是一位非常优秀的程序员 ， 那就应该阅读Knuth的TAOCP；如果你能读懂全部内容 ， 可以直接给我发送一份简历 。 据说Knuth前辈的言辞更加犀利：看不懂就别当程序员了！不过TAOCP对于新手来说 ， 阅读难度的确比较大 ， 书中的所有示例都使用了Knuth前辈自创的MIX汇编语言 。
阅读本文之前的提醒 要想彻底看懂本文 ， 有几个前提条件

  • 熟悉算法中的2个基础概念：时间复杂度、空间复杂度
    • 如果你压根没听过这2个概念 ， 说明你的算法基础完全为0 ， 真的没有在开玩笑！
    • 可以向公众号发送复杂度获取相关教程
  • 熟悉二进制和十进制的转换
    • 如果连这个都不熟悉的话 ， 那你的编程底子就真的需要好好补补啦
    • 可以向公众号发送进制获取相关教程
  • 熟悉常见的位运算操作
    • n & 1的结果是n最低二进制位的值 ， 也可以用于判断n的奇偶性
    • 求正整数n / 2 ， 可以用位运算取代：n >> 1
    • 如果不明白上述操作的原理 ， 可以向公众号发送位运算获取相关教程
什么是幂（Power）？ 众所周知 ， x的n次幂 ， 是指x的n次方 ， 也就是n个x相乘 ， 比如2的4次幂就是2 * 2 * 2 * 2 。
为了简化描述 ， 后面x的n次幂 ， 我就简化为x ^ n（本文中的 ^ 并不是按位异或的意思）
那如何通过编程求幂？假设只考虑x、n是整数且n大于等于0的情况 ， 最容易想到的方法如下所示
int power(int x, int n) {int result = 1;while (n-- > 0) {result *= x;}return result;} 这种方法的时间复杂度是O(n)、空间复杂度是O(1)
什么是快速幂？ 所谓快速幂 ， 就是用效率更高（时间复杂度更低）的方法求幂 ， 可以将时间复杂度优化至O(logn) 。
这里介绍2种求解方法：递归、非递归
一 ， 递归
[算法]程序员必学：快速幂算法
本文插图
根据上图中的等式 ， 不难写出以下代码
int fastPower(int x, int n) {if (n == 0) return 1;int result = fastPower(x, n >> 1);result *= result;return (n & 1) == 0 ? result : result * x;} 这个方法的时间、空间复杂度都是O(logn) 。
那如何分析出这个方法的复杂度呢？
如果你的算法功底比较薄弱 ， 可以代入特定值作一个大概的分析 ， 比如当n为16时 ， 方法的递归调用过程如下图所示


推荐阅读


上一篇：区块链：波场中国走向世界最完美的流通货币

下一篇：：Spektrum Firma 160 海模电调