怎么可以错过（快速幂运算pta）快速幂算法java，快速幂算法java语言实现幂运算|程序员必学，java求矩阵的n次幂，
文：小码哥教育明杰老师
前段时间有同学来私信我，想知道快速幂算法的内容，那么接下来就详细给大家讲一讲，内容较多，请耐心看完，相信一定会大家有所帮助！
1.关于快速幂
其实快速幂相关的问题，是参加算法竞赛（NOI、ACM等）的小伙伴必须要掌握的一小块基础内容。当然，就算你不打算参加算法竞赛，个人觉得只要你是一名程序员，就必须要掌握快速幂算法。
在《计算机程序设计艺术》一书中就有提到快速幂算法，此书的英文名是The Art of Computer Programming，简称TAOCP。
TAOCP出自Donald Ervin Knuth前辈之手。Knuth前辈是在计算机领域成就颇丰的知名科学家，是著名的KMP算法的发明人之一，在1974年获得“计算机领域的诺贝尔奖”：图灵奖（当年他才36岁）。目前TAOCP已经出版了第1、2、3、4A卷，按照计划，还有第4B、5、6、7卷未出版。第一卷首发于1968年，Knuth前辈今年是83岁高寿，据说他计划在105岁之前完成这部巨著。
关于TAOCP，微软创始人Bill Gates曾说过
If you think youre a really good programmer… read (Knuths) 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个基础概念：时间复杂度、空间复杂度如果你压根没听过这2个概念，说明你的算法基础完全为0，真的没有在开玩笑！可以先看看相关教程（建议观看P7~P11）熟悉二进制和十进制的转换如果连这个都不熟悉的话，那你的编程底子就真的需要好好补补啦可以先看进制相关教程（建议观看P28~P37）熟悉常见的位运算操作n & 1的结果是n最低二进制位的值，也可以用于判断n的奇偶性求正整数n / 2，可以用位运算取代：n >> 1如果不明白上述操作的原理，可以看位运算相关教程（建议观看P92~P101）
3.什么是幂（Power）？
众所周知，x的n次幂，是指x的n次方，也就是n个x相乘，比如2的4次幂就是2 * 2 * 2 * 2。
为了简化描述，后面x的n次幂，我就简化为x ^ n（本文中的 ^ 并不是按位异或的意思）
那如何通过编程求幂？假设只考虑x、n是整数且n大于等于0的情况，最容易想到的方法如下所示（这里采用的编程语言是Java，但没有涉及Java特殊的语法。所以就算你没用过Java，也可以看懂）
很显然，这种方法的时间复杂度是O(n)、空间复杂度是O(1)
4.什么是快速幂？
所谓快速幂，就是用效率更高（时间复杂度更低）的方法求幂，可以将时间复杂度优化至O(logn)。这里介绍2种求解方法：递归、非递归
4.1递归
根据上图中的等式，不难写出以下代码
这个方法的时间、空间复杂度都是O(logn)。
那如何分析出这个方法的复杂度呢？
如果你的算法功底比较薄弱，可以代入特定值作一个大概的分析，比如当n为16时，方法的递归调用过程如下图所示
不难看出，每次调用时，n的规模都减半，所以时间和空间复杂度都是O(logn)
如果你的算法功底还行，那就可以用更专业的方法去分析它的复杂度（没有一定的算法基础，可能会看不懂）
这其实是典型的应用分治策略的算法假设T(n)是数据规模为n时的时间复杂度，不难得出递推式：T(n) = T(n / 2) + O(1)最后通过主定理（Master Theorem）可以直接得出结论：T(n) = O(logn)4.2非递归
我们以求3 ^ 21为例子，来分析一下非递归的代码应该怎么写。
首先21的二进制形式是10101
不难得出以下结论
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，来决定是否要将它乘进最终结果代入3和21，fastPower(3, 21)的执行流程如下
4.2.1第1轮while循环
第4行代码n的二进制是10101（十进制是21）x = 3 ^ 1, 其对应二进制位的值是1（n的最后一个二进制位）所以需要执行第5行代码：将x乘进最终结果result = 3 ^ 1第7行代码x = (3 ^ 1) * (3 ^ 1) = 3 ^ 2第8行代码n右移1位，其二进制变成了1010（对应的十进制是啥？不重要！！！）4.2.2第2轮while循环
第4行代码n的二进制是1010x = 3 ^ 2, 其对应二进制位的值是0（n的最后一个二进制位）所以不需要执行第5行代码：不需要将x乘进最终结果result = 3 ^ 1第7行代码x = (3 ^ 2) * (3 ^ 2) = 3 ^ 4第8行代码n右移1位，其二进制变成了101（对应的十进制是啥？不重要！！！）4.2.3第3轮while循环
第4行代码n的二进制是101x = 3 ^ 4, 其对应二进制位的值是1（n的最后一个二进制位）所以需要执行第5行代码：将x乘进最终结果result = (3 ^ 1) * (3 ^ 4)第7行代码x = (3 ^ 4) * (3 ^ 4) = (3 ^ 8)第8行代码n右移1位，其二进制变成了10（对应的十进制是啥？不重要！！！）4.2.4第4轮while循环
第4行代码n的二进制是10x = 3 ^ 8, 其对应二进制位的值是0（n的最后一个二进制位）所以不需要执行第5行代码：不需要将x乘进最终结果result = (3 ^ 1) * (3 ^ 4)第7行代码x = (3 ^ 8) * (3 ^ 8) = 3 ^ 16第8行代码n右移1位，其二进制变成了1（对应的十进制是啥？不重要！！！）4.2.5第5轮while循环
第4行代码n的二进制是1x = 3 ^ 16, 其对应二进制位的值是1（n的最后一个二进制位）所以需要执行第5行代码：将x乘进最终结果result = (3 ^ 1) * (3 ^ 4) * (3 ^ 16)第7行代码x = (3 ^ 16) * (3 ^ 16) = 3 ^ 32第8行代码n右移1位，其二进制变成了04.2.6最后
由于n = 0，所以退出while循环最终result = (3 ^ 1) * (3 ^ 4) * (3 ^ 16)复杂度分析每执行一次while的循环体，n >>= 1, 会导致n的值减半所以时间复杂度：O(logn)、空间复杂度：O(1)5.Leetcode
Leetcode上的第50号题50. Pow(x, n)，刚好就可以用今天讲解的快速幂算法。以下是我的代码实现
需要提醒的是
这里我用的编程语言是Java，大家可以根据自己熟悉的编程语言，对一些语法细节作出相应的调整Leetcode上的n可能是个负数，所以上面的代码针对负数的情况作了一些处理6.更多快速幂相关的问题
时间有限，这篇文章就先说到这了哈。给小伙伴们留2个快速幂相关的问题，有空的话，可以去研究一下
使用矩阵快速幂求斐波那契数列请设计一个算法求x的y次幂模z的结果：(x ^ y) % z假设x、y都可能是很大的整数（y大于等于0，z不等于0）如果你特别希望我写点什么方面的内容，也可以留言建议，谢谢。
就讲这么多吧，希望内容对各位有帮助。
如果这篇文章看完，您觉得不错就请点个赞吧。
这样下次可以在浏览记录里，直接搜到这篇文章。
你们的赞也会鼓励我，继续更新更多干货。
祝你好运！
小码哥教育明杰老师。
多年软件开发经验和教学经验，尤其精通Android和iOS平台的开发，还开发了2个iOS的流行开源框架（MJRefresh、MJExtension），目前在国内的使用率非常高，之所以写【小码哥教育】公众号，是想用最简单的语言把复杂的技术说的通俗易懂，你能看到多大的世界，未来就有多大。
关注
和我的《小码哥教育干货区》，还有更多关于互联网IT技术实操分享，值得你一看。
本文系作者 @河马 原创发布在河马博客站点。未经许可，禁止转载。
暂无评论数据