实现Pow(x, n)

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • n 是一个整数
  • 要么 x 不为零，要么 n > 0 。
  • -104 <= xn <= 104

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function pow(x, n) {  
    // 处理负指数  
    if (n < 0) {  
        return 1 / pow(x, -n);  
    }  

    // 处理0次方的情况  
    if (n === 0) {  
        return 1;  
    }  

    let result = 1;  
    for (let i = 0; i < n; i++) {  
        result *= x;  
    }  
    return result;  
}  

// 使用示例  
console.log(pow(2, 3)); // 输出 8  
console.log(pow(2, -2)); // 输出 0.25  
console.log(pow(5, 0)); // 输出 1
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

快速幂算法：分治法

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    // 处理负指数的情况  
    if (n < 0) {  
        return 1 / myPow(x, -n);  
    }  
    // 处理0次方的情况  
    if (n === 0) {  
        return 1;  
    }  

    if (n % 2 === 0) {  
        // n 是偶数  
        const half = myPow(x, n / 2);  
        return half * half; // 合并子问题的结果  
    } else {  
        // n 是奇数  
        const half = myPow(x, (n - 1) / 2);  
        return x * half * half; // 合并子问题的结果  
    }  
};

循环实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function pow(x, n) {  
    // 处理负指数的情况  
    if (n < 0) {  
        x = 1 / x; // 将底数取倒数  
        n = -n;    // 将指数变为正数  
    }  
    
    let result = 1; // 初始化结果为1  
    while (n > 0) {  
        // 如果当前指数是奇数  
        if (n % 2 === 1) {  
            result *= x; // 将当前底数乘到结果中  
        }  
        // 更新底数  
        x *= x; // 底数的平方  
        // 更新指数  
        n = Math.floor(n / 2); // 指数除以2（向下取整）  
    }  
    
    return result;  
}  

// 使用示例  
console.log(pow(2, 10)); // 输出 1024  
console.log(pow(3, 3));  // 输出 27  
console.log(pow(2, -2)); // 输出 0.25

原理

  1. 归纳：快速幂算法的关键是将 x^n 表示为：

    • 如果 n 是偶数，那么
      $$
      x^n = (x^{n/2})^2
      $$

    • 如果 n 是奇数，那么
      $$
      x^n = x \cdot (x^{(n-1)/2})^2
      $$

  2. 递推：通过不断将 n 减半，我们能够在对数的时间内计算出结果。这意味着每次将问题规模缩小一半，明显减少了计算的次数。

分治算法特点

  • 分解：将问题分解为更小的子问题（例如，通过将指数减半）。
  • 解决：解决小规模的子问题（递归地计算更小的幂）。
  • 合并：将子问题的结果合并以获得原问题的解（通过平方根的形式合并计算结果）。

通过利用分治法的思想，快速幂算法显著提高了计算效率，特别是在处理大指数时。任何指数的计算都可以通过较大的子问题的解决及合并达到目的，最终结果只需通过对简单步骤的反复分解和组合就能够得出。

快速幂算法的复杂度分析主要集中在时间复杂度和空间复杂度两个方面。

快速幂算法的复杂度分析主要集中在时间复杂度和空间复杂度两个方面。

时间复杂度

快速幂算法的时间复杂度为 O(log n) 。这一复杂度来源于以下几个方面：

  1. 问题规模的减小：每一步操作中，进制数 ( n ) 通过整除 2 的方式减小一半（即 ( n = n / 2 )）。因此，经过 ( k ) 次操作后，( n ) 的大小大致为 ( n/2^k )。

  2. 次数计算：为了将 ( n ) 减小到 1，需要进行的操作次数 ( k ) 满足以下不等式：
    $$
    \frac{n}{2^k} \leq 1 \Rightarrow n \leq 2^k \Rightarrow k \geq \log_2(n)
    $$
    这表示实际计算所需的步骤数是与 ( n ) 的对数成正比。

因此，综合以上分析，快速幂算法的时间复杂度是 O(log n) 。

空间复杂度

空间复杂度方面，快速幂算法的实现通常是递归的，递归调用所需的空间取决于递归的深度：

  1. 在最坏的情况下（即 ( n ) 是大奇数），递归的最大深度大约为 O(log n) 。

  2. 因此，递归实现的空间复杂度为 O(log n) 。如果采用循环实现来代替递归，则空间复杂度可以提升到 O(1) ，也就是常数空间复杂度。

小结

  • 时间复杂度：O(log n)
  • 空间复杂度：递归实现为 O(log n) ，循环实现为 O(1)