按常理的算法是复杂度为O(n)如果再降低便是O(nlgn)
O(n)
static int pow(int a, int n) {
int res = 1;
for (int i = 0; i < n; i++) {
res *= a;
}
return res;
}
O(nlgn)
/**
* 以最快速度求a的n次方
* O(lgn)
*/
public static int ex(int a, int n) {
if (n == 0) return 1;
if (n == 1) return a;
int temp = a; //a 的 1 次方
int res = 1;
int exponent = 1;
while ((exponent << 1) < n) {
temp = temp * temp;
exponent = exponent << 1;
}
res *= ex(a, n - exponent);
return res * temp;
}
二进制巧算
/**
* m=1010
*/
public static long ex2(long n, long m) {
if (n == 0) return 1;
long pingFangShu = n; //n 的 1 次方
long result = 1;
while (m != 0) {
//遇1累乘现在的幂
if ((m & 1) == 1)
result *= pingFangShu;
//每移位一次,幂累乘方一次
pingFangShu = pingFangShu * pingFangShu;
//右移一位
m >>= 1;
}
return result;
}
本文作者:Author: 寒光博客
文章标题:快速幂运算( 未填坑 矩阵快速幂求解斐波那契数列 )
本文地址:https://dxoca.cn/Algorithm/200.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/200.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。