最简单的方法就是一个for循环搞定，和明显我的效率为O(n)，那么，这个如果用来做对数器还是不错的，那么我们可不可以提升效率呢，当然可以啦，用分治法的话为O(logn)，下面给出算法例子以及普通方法的对数器;

为什么我们的效率是O(lgN)呢?

我们按递归的公式T(n)=aT(n/b)+f(n)，由下面的算法可以知道，因为我们只算了一半，所以我们的a=1，b=2，因为相乘是常数时间，所以我们的公式可以变为;

T(n)=T(n/2)+O(1)

很明显，根据master公式，O(n^logb(a))=O(1) 跟O(f(n))是相同的，所以时间复杂度为：O(f(n)logn)，也就是O(logn)比O(n)快。

本质上快在只需要算一半即可。

package cn.myforever.test;
public class DivideAndConquer {
    /**
     * 计算x^n的乘方
     * @param x
     * @param n
     * @return
     */
    public static int power(int x,int n) {
        //分成左右两边
        int result = getValue(x,0, n-1);
        return result;
    }
    public static int getValue(int x,int l,int r) {
        if(l>=r) {
            return x;
        }
        //这里只需要算一半的即可
        if(r%2==1) {
            int getLeft = getValue(x,l,(r+l)/2);
            return getLeft*getLeft;
        }else {
            //因为这里多减去了一个，所以这边要多乘上一个x
            int getRight = getValue(x,l,(r+l-1)/2);
            return getRight*getRight*x;
        }
    }
    /**
     * 构造一个对数器，来验证值是否正确
     * @param args
     */
    //2、上面已经有测试方法，下面构造一个绝对正确的方法
    public static int getYes(int x,int n) {
        int result =1;
        for (int i = 0;i < n; i++) {
            result=result*x;
        }
        return result;
    } 
    //构造一个随机数产生器
    public static int[] getXN(int xSize,int nSize) {
        int x =(int) (Math.random()*(xSize)+1);
        int n =(int) (Math.random()*(nSize)+1);
        int[] xn = new int[2];
        xn[0]=x;
        xn[1]=n;
        return xn;
    }
    public static void main(String[] args) {
        System.out.println(power(2, 4));
        int times =10000;
        int xSize =10;
        int nSize =10;
        boolean flag = true;
        for (int i = 0; i < times; i++) {
            int[] xn = getXN(xSize,nSize);
            int result1 = power(xn[0], xn[1]);
            int result2 = getYes(xn[0], xn[1]);
            System.out.println("x:"+xn[0]+";n:"+xn[1]+";result1="+result1+";result2="+result2);
            if(result1!=result2) {
                flag = false;
                System.out.println("x:"+xn[0]+";n:"+xn[1]);
                break;
            }
        }
        System.out.println(flag?"完全正确":"出错了");
    }
}