LeetCode Pow(x, n) 快速冪算法：遞歸與迭代實現全解析

問題描述

實現 pow(x, n) 函數，計算 x 的 n 次方。n 為 32 位有符號整數，需處理負指數情況。暴力循環 O(n) 會超時，必須使用 O(log n) 的快速冪算法。

核心思想：分治遞歸

利用指數運算性質：x^n = (x^(n/2))^2（n 為偶數），x^n = x * (x^(n/2))^2（n 為奇數）。每次將指數減半，遞歸深度 log n。

三種經典實現

1. 遞歸實現（最簡潔）

class Solution {
public:
    double myPow(double x, long long n) {
        if (n == 0) return 1.0;
        if (n < 0) return 1.0 / myPow(x, -n);
        double half = myPow(x, n / 2);
        return (n % 2 == 0) ? half * half : half * half * x;
    }
};

2. 迭代實現（位運算優化）

class Solution {
public:
    double myPow(double x, long long n) {
        if (n < 0) { x = 1 / x; n = -n; }
        double res = 1.0;
        while (n > 0) {
            if (n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
};

3. 處理 INT_MIN 邊界情況

n = -2147483648 時，-n 會溢出。解決方案：使用 long long 類型接收 n，或特殊處理 n == INT_MIN。

關鍵點總結

• 時間複雜度 O(log n)，空間複雜度遞歸 O(log n)，迭代 O(1)
• 負指數轉為正指數計算倒數
• 迭代版本利用二進制分解：n = Σ 2^i，對應位為 1 時累乘
• 注意 double 精度問題，大指數可能產生無窮大或下溢

擴展應用

快速冪思想廣泛應用於矩陣冪、模冪運算（如 RSA 加密）、幾何級數求和等問題。掌握其遞歸與迭代雙重實現是算法面試必備技能。