a=a*a快速幂

2019-04-13 22:03发布

站内文章 / 模拟电子
17756 0 1045
今天在刷题的时候，看到一个快速幂的算法，因为之前没接触过，所以就蒙蔽了几分钟
一开始想的是为什么求幂要移位啥的这么麻烦，不是b个a相乘就完事了嘛 后来了解到这是快速幂算法，一开始我们的求幂算法是这样的： private int power(int a, int b) { int temp=1; for(int i=0;i简单粗暴，就是b个a相乘，但是这样在数规模大的时候可能有超时问题！ 就比如我们在心算 2^4时候，我们并不会真正去算2^3，而是  (2^2)^2=16 而快速幂算法就是利用二进制让我们少算一些东西，从而提高速度 原理是这样的：（没学专门画数学公式的软件，丑请见谅）
可以把a^2^i这些看出是基，能够把时间复杂度从 n 降到 log(n)是因为基是可以递推的，就是说你知道一个基，把它平方就是下一个基 结合移位和逻辑运算等知识，就可以写出代码： private int power2(int a, int b) { int base=1; //base可以理解为基 while(b!=0) { if((b&1)==1) //如果最低位为1，则乘以基；为0，不乘 base*=a; a*=a; // 基的平方 等于 下一个基 b=b>>1; //右移一位 } return base; }在大规模问题下，快速幂算法较普通算法还是可观的

热门文章