快速幂算法详解：高效计算 x 的 n 次幂

快速幂算法详解

在算法面试和实际开发中，我们经常需要计算一个数的整数次幂。例如 LeetCode 50 题要求实现 pow(x, n)，即计算 x 的 n 次幂。

问题描述

给定浮点数 x 和整数 n，返回 x^n 的值。

示例：

• 输入：x = 2.00000, n = 10

• 输出：1024.00000

• 输入：x = 2.10000, n = 3

• 输出：9.26100

• 输入：x = 2.00000, n = -2

• 输出：0.25000

暴力解法的局限

最直观的想法是循环遍历 n 次，每次将结果乘以 x。当 n 很大时（例如 10^9），这种 O(n) 的时间复杂度会导致超时。

快速幂原理

快速幂的核心思想是分治法。通过观察数学规律，我们可以将指数减半来减少计算量。

假设我们要计算 x^n：

1. 当 n 为偶数时：x^n = (x^(n/2)) * (x^(n/2))
2. 当 n 为奇数时：x^n = (x^(n/2)) * (x^(n/2)) * x

递归出口是 n = 0，此时返回 1。

这样，每次递归都将规模减半，时间复杂度从 O(n) 降低到了 O(log n)。

代码实现

以下是基于 Java 的递归实现。注意处理负指数的情况，将其转换为正指数并取倒数。

class Solution {
    public double myPow(double x, int n) {
        // 处理负指数：x^-n = 1 / x^n
        return n < 0 ? 1.0 / pow(x, -n) : pow(x, n);
    }

    private double pow(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        
        // 递归计算一半
        double tmp = pow(x, n / 2);
        
        // 根据奇偶性决定是否需要额外乘一次 x
         n %  ==  ? tmp * tmp : tmp * tmp * x;
    }
}