java快速求幂算法

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; 5¹⁰⁼⁽⁵2)^5 ; (5²⁾5=(5⁴⁾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）