首页 > 其他 > 详细

快速幂求解

时间:2017-04-01 12:46:12      阅读:219      评论:0      收藏:0      [点我收藏+]

顾名思义,快速幂就是快速算底数的n次幂。其时间复杂度为 O(log?N), 与朴素的O(N)相比效

用法:用于求解 a 的 b 次方,而b是一个非常大的数,用O(n)的复杂度会超时。那么就需要这个算法,注意它不但可以对数求次幂,而且可用于矩阵快速幂。

把b转换成二进制数,该二进制位数有logb位;该二进制数第i位的权为2i-1
 
例如:
技术分享     11的二进制是1011
11 = 23×1 + 22×0 + 21×1 + 2o×1
因此,我们将a11转化为算技术分享
 
 

快速幂求解

原文:http://www.cnblogs.com/lezhifang/p/6655295.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!