Pow(x, n)

Implement pow(x, n).

如果直接一个一个乘的话太慢,用二分法可以达到logN的复杂度,用递归求pow(x, n) = pow(x, n/2) * pow(x, n/2) * pow(x, n%2),要注意n<0要单独处理,另外算/2的时候用位运算更快。

public class Solution {
    public double pow(double x, int n) {
            double temp = powerAbs(x, Math.abs(n));
            return (n < 0)? 1.0/temp : temp;
    }
    
    public double powerAbs(double x, int n) {
        if ( n == 0) {
            return 1;
        }
        double temp = pow(x, n >> 1);
        temp *= temp;
        return ((n & 1) == 1)? temp*x : temp;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s