50. Pow(x, n)

題目網址：https://leetcode.cn/problems/powx-n/

題意：給一 double x 和一整數 n, 返回 x 的 n 次方。

Solution：

想法：利用 Divide and Conquer, 比如 $2^{10}$ 可拆成 $2^5 * 2^5$, 而 $2^5$ 又可拆成 $2(2^2 * 2^2)$, 依此類推。透過這樣的方法可以避免重複計算, 而不用一直乘 x

class Solution {
public:
    double myPow(double x, int n) {
        // 注意 res 要宣告成 double (容易粗心)
        double res = quickPow(x, abs(n)); // 計算 x^n, 其中 n 取正
        return (n >= 0) ? res : (1 / res); // 若 n < 0, 則取倒數 1 / (x^n)
    }

private:
    double quickPow(double x, int n){
        // 0^n = 0
        if (x == 0) {
            return 0;
        }

        // x != 0, 則 x^0 = 1
        if (n == 0) {
            return 1;
        }

        const double half = quickPow(x, n / 2); // 計算 x^(n / 2), 注意 half 的 data type
        // 若 n 為奇數, 則前面還要再多乘一次 x
        return (n % 2) ? (x * half * half) : (half * half);
    }
};

• time：$O(log(n))$ ➔ $T(n)$ = $2 \cdot T(\dfrac{n}{2})$ + $O(1)$
• space：$O(log(n))$ ➔ 取決於遞迴深度, 遞迴深度不超過 $log(n)$