Pow(x, n)

Pow(x, n)

出处

Implement pow(x, n)

Solution

由于pow(x, n)相当于n个x相乘，左半边乘积与右半边相互独立且类似，所以可以用D&C策略进行二分。注意，二分之后需要处理n大于0，等于0，小于0等情况。

Complexity

时间复杂度 O(n), 空间复杂度 O(logn)

Code

double pow(double x, int n) {      
    if (n == 0)
        return 1.0;
    if (x == 0)
        return 0.0;
    double half = pow(x,n/2);
    if(n%2 == 0)
        return half*half;
    else if(n > 0)
        return half*half*x;
    else
        return half*half/x;
}