1.引言
快速求幂算法是java算法与数据结构后面的习题。据说这个题目被当做面试考过。正好我也不懂，然后就看了下，于是来记录一下。
2.正文
在学习java的时候，一般做阶乘(阶乘数不是很高)都是按照如下的代码：
//a是底数，b是阶数
public double factorial (double a,int b){
double sum=1d;
for (int i=1;i<=b;i++){
sum=sum*a;
}
return sum;
}
这种算法明显有问题。假如阶乘是100次，那么要乘100次。时间效率底下。
我要说的这个算法的精髓是这样的：假如要求5^11的值。我们把阶数每次循环一次除以2。例如 5^11= 5 x 5^10; 510=(52)^5 ; (52)5=(54)2 x 5;依次这样分解下次得到的结果是5^8 x 5^2 x5^0 。 递归算法如下
public double power(double a,int b){
if (b==0)return 1;
if (b==1)return a;
if ((b&1)==0)return power(a*a,b>>1);
else return a*power(a*a,b>>1);
}
根据递归算法写一个非递归算法。
public double power1(double a,int b){
double result=1d;
if (b==0)return 1;
if (b==1)return a;
while (b>0){
if ((b&1)==1){
result=result*a;
}
a=a*a;
b=b>>1;
}
return result;
}
根据循环进行的次数可以看出。时间复杂度为O（logn）
