算法笔记1
快速幂
时间复杂度为 O(logN),比朴素的方法快很多
核心思想是减少乘法的次数
比如:
朴素方法:需要乘9次
快速幂:
1. 递归版(慢于迭代)
思想:拆分
当指数n为偶数:
= 当指数n为奇数:
= *
int fastpow1(int a,int n){
if(n == 0)
return 1;
if(n == 1)
return a;
//注意:这里必须缓存下来,这样才保证只算了一次,否则多次计算,又变回了朴素方法
long long int t = fastpow1(a, n / 2);
if((n & 1) == 0){
//偶数
return t * t % MOD;
}else{
//奇数
return t * t % MOD * a % MOD;
}
}
2. 迭代版(建议使用)
11的二进制码: 1011
=
=
=
对于每一项(第三行):
而
而
而
......依此类推
对于11的二进制码:1011
最后乘积的结果,
而对于每一项,
那么我们需要检测每个bit位,可以使用>>,然后与1&,即可判断
int fastpow2(int a,int n){
long long int t = a;
int res = 1;
//当n == 0时,说明所有1的项都乘了,即得到了结果
while(n){
//检查最低为是否为1,为1则乘以该项
if(n & 1){
res = res * t % MOD;
}
//t对应 a^(2^i),平方使得i++,即得到下一项
t = t * t % MOD;
//右移1位,用以检测
n >>= 1;
}
return res;
}