JS 笔试题——Pow(x, n)

题目：实现 ，即计算 的 次幂函数（即，）。

示例 1：

输入：x = 2, n = 10
输出：1024

示例 2：

输入：x = 2.1, n = 3
输出：9.261

示例 3：

输入：x = 2, n = -2
输出：0.25
解释：2^(-2) = 1/2^2 = 1/4 = 0.25

方法： 递归

分析：

可以分解为 ...

所以先找到 的结果再逐级返回结果。
但是时，需要处理奇偶两种情况：

完整代码：

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    let m = n;
    return m >= 0 ? quickMul(x, m) : 1 / quickMul(x, -m);
};

var quickMul = function (x, m) {
    if (m === 0) {
        return 1;
    }
    let res = quickMul(x, Math.floor(m / 2));
    return m % 2 === 0 ? res * res : res * res * x;
}

复杂度分析

• 时间复杂度：，即为递归的层数。
• 空间复杂度：，即为递归的层数。这是由于递归的函数调用会使用栈空间。