LeetCode Pow(x, n)：分治法快速冪 O(log n) 實現

題目回顧

實現 pow(x, n)，即計算 xⁿ。n 可為負整數。

分治遞推公式

xⁿ = (xⁿ/²)²           (n 為偶數)
xⁿ = (xⁿ/²)² × x       (n 為奇數)
x⁰ = 1
x⁻ⁿ = 1 / xⁿ

遞歸深度 log₂|n|，時間 O(log n)。

C++ 代碼

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n < 0) return 1 / power(x, -(long long)n); // 注意 INT_MIN 取絕對值溢出
        return power(x, n);
    }
    
private:
    double power(double x, long long n) {
        if (n == 0) return 1;
        double half = power(x, n / 2);
        if (n % 2 == 0) return half * half;
        else return half * half * x;
    }
};

關鍵細節

1. INT_MIN 處理：n = -2147483648 時 -n 溢出，用 long long 接收
2. 遞歸終止：n == 0 返回 1
3. 奇偶判斷：n % 2 或 n & 1

迭代版快速冪（二進制分解）

double myPow(double x, int n) {
    long long N = n;
    if (N < 0) { x = 1 / x; N = -N; }
    double ans = 1;
    while (N > 0) {
        if (N & 1) ans *= x;
        x *= x;
        N >>= 1;
    }
    return ans;
}

複雜度

• 時間：O(log |n|)
• 空間：遞歸版 O(log n) 棧，迭代版 O(1)

運行結果示例