快速幂

pow(x,y)快速幂的实现形式

如果我们使用常规的想法去累成得到无疑时间复杂度很高，我们再进行对问题的分析，加入我们相求x^n的值，那我们只要知道x^1/2的值，继续递归知道我们知道x^1的值，那么我们在返回栈结果我们就可以的到我们想要的结果时间复杂度从n降到logn
解题细节：
首先y可能为负值，那么我们预处理一下，当y小于零时，令y=-y，x=1/x
其次我们要讨论n的奇偶性，当n为偶数时，那么x^n = half * half，当n为奇数时,那么x^n = half * half * x;其中half表示x^n的一半
代码实现：

class Solution {
    public double myPow(double x, int n) {
        if(n<0) {
			n = -n;
			x = 1/x;
		}
		return fastPow(x, n);
    }
    public double fastPow(double x,int n) {
		if( n == 0) {
			return 1.0;
		}
		double half = fastPow(x,n/2);
		if(n%2 == 0) {
			return half*half;
		}else {
			return half*half*x;
		}
	}
}