[LC50] Pow(x, n)

Tuesday, January 8, 2019

这道算法题来自 LeetCode #50:实现 x 的 n 次方结果。这里不能使用标准库函数,而且 n 值可能很大,但不超过 32 位整型范围。

暴力相乘

求 $x$ 的 $n$ 次方,即对 $x$ 执行 $n$ 次乘法即可。

let result = 1
let count = Math.abs(n)

while (count > 0) {
  result = result * x
  count--
}

return n > 0 ? result : 1 / result

复杂度分析

  • 时间复杂度:因为要执行 ‌n 次乘法,所以时间复杂度为 $O(n)$

分而治之

divide & conquer

先把 $n$ 个 $x$ 逐次分成一半,即 $x^{n}$ -> $x^{n/2}$ -> $x^{n/4}$ -> $…$ -> $x^1$;拆分到最后,再返回计算乘积。计算时,需要分三种情况:

  • 若 $n$ 为负数,则有 $1/pow(x, -n)$
  • 若 $n$ 为偶数,则有 $pow(x, n/2) * pow(x, n/2)$,即 $x^{n/2} * x^{n/2}$;简化式子可得 $(x * x)^{n/2}$ 即 $pow(x * x, n / 2)$,
  • 若 $n$ 为奇数,则有 $pow(x, (n-1)/2) * pow(x, (n-1)/2) * x$,即 $x^{(n-1)/2} * x^{(n-1)/2} * x$;简化式子可得 $x^{n-1} * x$,即 $pow(x, n - 1) * x$
var myPow = function(x, n) {
    if (n === 0) return 1
    if (n === 1) return x
    
    if (n < 0) {
        return 1 / myPow(x, -n)
    }
    
    if (n % 2 === 0) {
        return myPow(x * x, n / 2)
    } else {
        return myPow(x, n - 1) * x
    }
};

复杂度分析

  • 时间复杂度:由于对 $n$ 个数折半处理,每次处理只做一次操作,所以时间复杂度为 $O(logN)$