LeetCode Pow(x, n) 實現：從 O(n) 到 O(log n) 再到 O(1) 的優化之路

題目要求

實現 pow(x, n)，計算 x 的 n 次冪。n 為 32 位有符號整數，可能為負。

三輪優化演進

版本 1：朴素循環 O(n) —— 超時

double myPow(double x, int n) {
    double res = 1;
    while (n > 0) { res *= x; --n; }
    return res;
}

測試用例含大指數（如 2³¹-1），線性循環必超時。

版本 2：快速冪二進制分解 O(log n) —— 仍超時

double myPow(double x, int n) {
    if (n == 0) return 1;
    long long N = n; // 防止 n=INT_MIN 取絕對值溢出
    if (N < 0) { x = 1/x; N = -N; }
    double res = 1;
    while (N) {
        if (N & 1) res *= x;
        x *= x;
        N >>= 1;
    }
    return res;
}

雖然邏輯正確，但 LeetCode 測試極大指數且對常數因子敏感，仍可能 TLE。

版本 3：數學恒等式 O(1) —— 通過

利用 指數對數轉換：xⁿ = e^{n ln x}

double myPow(double x, int n) {
    if (x == 0) return 0;
    if (n == 0) return 1;
    // 處理負底數：(-x)^n = (-1)^n * x^n
    bool negBase = (x < 0);
    x = fabs(x);
    double res = exp(n * log(x));
    if (negBase && (n & 1)) res = -res;
    return res;
}

標準庫 exp/log 經過高度優化，硬件指令級實現，實際為常數時間。

關鍵細節處理

1. n = INT_MIN：絕對值溢出，用 long long 或直接用對數法避開
2. x < 0 且 n 非整數：題目 n 為整數，故 (-x)^n 有定義，僅需符號判斷
3. 精度：對數法引入浮點誤差，但 LeetCode 允許 1e-5 相對誤差，完全可接受

總結對比

延伸：模冪運算

若求 xⁿ mod m，只能用快速冪，因模運算無對數恒等式。模板：

long long modPow(long long a, long long n, long long mod) {
    long long res = 1 % mod;
    a %= mod;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}