【算法技巧之快速幂运算】Pow(x,n)

原链接：https://leetcode-cn.com/leetbook/read/leetcamp-2/aa4r31/

题目：实现 pow(x,n)，即计算 x 的 n 次幂函数（即，xn ）。

示例1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例2：

输入：x = 2.10000, n = 3
输出：9.26100

示例3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

快速幂是一个非常经典的问题，对于求,有一个O(n)暴力解法：

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    let res = 1;
    for(let i=0;i<n;i++){
        res *= x;
    }
    return res;
};

但实际上有一个更有效的解法-O(logn)快速幂，对于，我们有

• 假设b是偶数，此时使x == b-x，则两个问题为同一个问题，都是；
• 假设b是奇数，此时先计算，将结果单独乘

快速幂解法：

var myPow = function(x, n) {
    const fun = (n) => {
        if(Math.sign(n)===0){
            return 1;
        }
        let res = fun(Math.floor(Math.abs(n)/2));
        res *= res;
        if(Math.abs(n) % 2 === 1){
            res *= x;
        }
        if(Math.sign(n) > 0){
            return res;
        }
        if(Math.sign(n) < 0){
            return 1 / res;
        }
    }
    return fun(n);
};