Skip to content

Latest commit

 

History

History
110 lines (81 loc) · 2.56 KB

50. Pow(x, n).md

File metadata and controls

110 lines (81 loc) · 2.56 KB
title toc date tags top
50. Pow(x, n)
false
2017-10-30
Leetcode
Math
Binary Search
50

题目

Implement $\text{pow}(x, n)$, which calculates $x$ raised to the power $n$($x^n$).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

  • $-100.0 < x < 100.0$
  • $n$ is a 32-bit signed integer, within the range [−$2^{31}$, $2^{31}$ − 1]

分析

最直接的方式当然是$O(n)$的算法,将$x$乘以或者除以$n$次,

double myPow(double x, int n) {
    if (x == 0) return x;
    x = x > 0 ? x : 1.0/x;
    double res = x;
    for (int i = 1; i < n; i++) res *= x;
    return res;
}

可惜的这种方法超时了,稍微想一想就知道当$n$很大的时候,这种解法肯定是不行的。

另一种方法是使用分治算法,在这里,分治算法的递归公式为

$$x^n = x^{(n/2)} \times x^{(n/2)} \times x^{(n%2)}$$

最差运行时间$T(n)$用递归表达式表达为

$$T(n) = T(n/2)\times T(n/2) \times T(n%2) $$

因为$n/2$和$n%2$的最终结果只有0,-1,1三种,所以只考虑这三种base case.

public double myPow(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    if (n == -1) return 1.0 / x;
    double y = myPow(x, n / 2);
    return y * y * myPow(x, n % 2);
}

下面用位操作来计算。考虑$n$的二进制表示. 例如, 如果$n$是 "10001011", 则 $x^n = x^{1+2+8+128} = x^{1} \times x^{2} \times x^{8} \times x^{128}$. 因此, 我们不用循环$n$次来计算$x^n$. 为了加快计算, 我们遍历$n$中的每一位, 如果第$i$位是1, 我们把结果乘以$x^{2^i} = x^{(1 << i)}$. 既然 $(1 &lt;&lt; i)$是2的指数, $x^{(1&lt;&lt;(i+1))}$ = square($x^{(1&lt;&lt;i)}$). 这个循环最多执行$\log(n)$次, i.e.$n$的二进制表示中最多有$\log(n)-1$位1).

public double myPow(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    if (n < 0) {
        // 不能直接 n = -n, 当n = -2147483648
        if (n == Integer.MIN_VALUE) {
            return 1 / myPow(x, Integer.MAX_VALUE) / x;
        } else {
            x = 1.0/x;
            n = -n; //防止溢出
        }
    }

    double res = 1;
    while (n > 0) {
        // n的第i位是1
        if ((n & 1) > 0)
            // res *= x^(1 << i)
            res *= x;
        // n 右移一位
        n >>= 1;
        x = x*x;
    }
    return res;
}