LeetCode 50 - Pow(x, n)（快速幂算法）

问题描述

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

示例 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/2^2 = 1/4 = 0.25

约束条件：

$-100.0 < x < 100.0$
$-2^{31} \leq n \leq 2^{31}-1$
$n$ 是一个整数
$-10^4 \leq x^n \leq 10^4$

解题思路

核心算法：快速幂（Fast Power）

这道题的核心是使用快速幂算法，也称为二进制幂算法。这是一个经典的数学优化技巧，可以将幂运算的时间复杂度从 $O(n)$ 优化到 $O(\log n)$。

关键洞见： 任何整数都可以表示为二进制形式，利用这个性质可以将幂运算分解为多个平方运算的组合。

算法原理

二进制分解：将指数 n 转换为二进制形式
平方递推：利用 $x^{2k} = (x^k)^2$ 的性质
累乘结果：根据二进制位是否为 1 决定是否累乘

具体步骤

处理负数指数：如果 n < 0，将 x 取倒数，n 取绝对值
初始化：设置 base = x，result = 1
循环处理：当 n > 0 时：
- 如果 n 的最低位为 1，将 base 乘到 result 中
- base 自乘（相当于 base = base²）
- n 右移一位（相当于 n = n/2）
返回结果：最终 result 即为 $x^n$

数学推导

对于任意正整数 n，可以表示为：
$$n = \sum_{i=0}^{k} b_i \cdot 2^i$$

其中 $b_i \in {0, 1}$ 是 n 的二进制表示。

因此：
$$x^n = x^{\sum_{i=0}^{k} b_i \cdot 2^i} = \prod_{i=0}^{k} x^{b_i \cdot 2^i} = \prod_{i=0}^{k} (x^{2^i})^{b_i}$$

实现细节

位运算技巧

n & 1：检查 n 的最低位是否为 1
n >>= 1：将 n 右移一位，相当于 n/2
每次循环 base 自乘，相当于计算 $x^{2^i}$

边界情况处理

n = 0：任何数的 0 次方都是 1
n < 0：转换为正数处理，最后取倒数
x = 0：0 的任何正次方都是 0，0 的 0 次方是 1
n = -2^31：需要特殊处理，因为取绝对值会溢出

代码实现

func myPow(x float64, n int) float64 {
    // 处理边界情况
    if n == 0 {
        return 1.0
    }
    
    // 处理负数指数
    if n < 0 {
        x = 1 / x
        n = -n
    }
    
    base := x
    res := 1.0
    
    // 快速幂算法
    for n > 0 {
        // 如果当前位为 1，累乘到结果中
        if n&1 == 1 {
            res *= base
        }
        // base 自乘，相当于 base = base²
        base *= base
        // n 右移一位，相当于 n = n/2
        n >>= 1
    }
    
    return res
}

执行过程示例

以计算 $2^{10}$ 为例：

初始：base = 2, res = 1, n = 10 (二进制：1010)

第1轮：n = 10 (1010)
- n&1 = 0，不累乘
- base = 2² = 4
- n = 5 (101)

第2轮：n = 5 (101)  
- n&1 = 1，res = 1 × 4 = 4
- base = 4² = 16
- n = 2 (10)

第3轮：n = 2 (10)
- n&1 = 0，不累乘
- base = 16² = 256
- n = 1 (1)

第4轮：n = 1 (1)
- n&1 = 1，res = 4 × 256 = 1024
- base = 256² = 65536
- n = 0，结束

结果：1024

方法比较

方面	暴力法	快速幂算法
时间复杂度	$O(n)$	$O(\log n)$
空间复杂度	$O(1)$	$O(1)$
优点	简单直观	高效，适合大指数
缺点	效率低，容易超时	实现稍复杂
推荐度	★★☆☆☆	★★★★★

复杂度分析

时间复杂度：$O(\log n)$

每次循环 n 都会减半（右移一位）
循环次数等于 n 的二进制位数
对于 32 位整数，最多循环 32 次

空间复杂度：$O(1)$

只使用了常数个变量
不依赖输入规模

数学证明

设 n 的二进制位数为 k，则：
$$k = \lfloor \log_2 n \rfloor + 1$$

因此时间复杂度为 $O(\log n)$。

关键收获

重要概念

快速幂算法：将幂运算的时间复杂度从线性优化到对数级
二进制分解：利用整数的二进制表示进行算法优化
位运算技巧：使用位运算进行高效的数值操作

常见陷阱

整数溢出：当 n = -2^31 时，取绝对值会溢出
精度问题：浮点数运算可能存在精度误差
边界情况：需要正确处理 n = 0 和 x = 0 的情况

扩展思考

快速幂算法的思想可以扩展到：

矩阵快速幂：计算矩阵的高次幂
多项式快速幂：计算多项式的幂
模运算快速幂：在模运算下计算幂

这个算法是数学计算中的经典优化技巧，在面试中经常被考察，掌握它对于解决相关问题非常有帮助。

Adrian Wang's blog