⚡ pow(x, n) アルゴリズム解析

🔧 実装コード

/**
 * x を n 乗する関数
 * 高速指数演算（Fast Exponentiation）を使用してO(log n)で計算
 *
 * @param {number} x - 底となる数値 (-100.0 < x < 100.0)
 * @param {number} n - 指数となる整数 (-2^31 <= n <= 2^31-1)
 * @return {number} x^n の結果
 */
var myPow = function(x, n) {
    // 負の指数の場合、1/x の |n| 乗として計算
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }

    /**
     * 再帰による高速指数演算の実装
     *
     * @param {number} base - 底
     * @param {number} exp - 指数（非負）
     * @return {number} base^exp の結果
     */
    function fastPow(base, exp) {
        // ベースケース：指数が0の場合は1を返す
        if (exp === 0) return 1;

        // 指数が偶数の場合：x^n = (x^2)^(n/2)
        if (exp % 2 === 0) {
            const half = fastPow(base, Math.floor(exp / 2));
            return half * half;
        }
        // 指数が奇数の場合：x^n = x * x^(n-1)
        else {
            return base * fastPow(base, exp - 1);
        }
    }

    return fastPow(x, n);
};

📊 計算量比較

🌳 アルゴリズムの動作（例：2^10）

🎮 インタラクティブデモ