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

高速指数演算（Fast Exponentiation）の詳細解析

🔧 実装コード

/** * 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); };

📊 計算量比較

手法 時間計算量 空間計算量 n=1000の場合の計算回数
単純な反復 O(n) O(1) 1000回
高速指数演算 O(log n) O(log n) 約10回

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

fastPow(2, 10)
↓ 10は偶数
fastPow(2, 5) × fastPow(2, 5)
↓ 5は奇数
2 × fastPow(2, 4)
↓ 4は偶数
fastPow(2, 2) × fastPow(2, 2)
↓ 2は偶数
fastPow(2, 1) × fastPow(2, 1)
↓ 1は奇数
2 × fastPow(2, 0)
↓ 0はベースケース
1

📝 ステップバイステップ解析

Step 1: 負数処理

n < 0 の場合
x = 1/x, n = -n

Step 2: ベースケース

exp === 0
return 1

Step 3: 偶数の場合

exp % 2 === 0
half² を返す

Step 4: 奇数の場合

exp % 2 === 1
base × fastPow(base, exp-1)

🔍 具体例の詳細解析

例1: myPow(2, 10) = 1024

計算過程を読み込み中...
fastPow(2, 10) - 偶数なので半分に分割
fastPow(2, 5) - 奇数なので base × fastPow(base, exp-1)
fastPow(2, 4) - 偶数なので半分に分割
fastPow(2, 2) - 偶数なので半分に分割
fastPow(2, 1) - 奇数なので base × fastPow(base, exp-1)
fastPow(2, 0) = 1 (ベースケース)
= 2 × 1 = 2
= 2 × 2 = 4
= 4 × 4 = 16
= 2 × 16 = 32
= 32 × 32 = 1024
最終結果: 2^10 = 1024

例2: myPow(2.1, 3) = 9.261

計算過程を読み込み中...
fastPow(2.1, 3) - 奇数なので base × fastPow(base, exp-1)
fastPow(2.1, 2) - 偶数なので半分に分割
fastPow(2.1, 1) - 奇数なので base × fastPow(base, exp-1)
fastPow(2.1, 0) = 1 (ベースケース)
= 2.1 × 1 = 2.1
= 2.1 × 2.1 = 4.41
= 2.1 × 4.41 = 9.261
最終結果: 2.1^3 = 9.261

例3: myPow(2, -2) = 0.25

計算過程を読み込み中...
負の指数処理: x = 1/2 = 0.5, n = 2
fastPow(0.5, 2) - 偶数なので半分に分割
fastPow(0.5, 1) - 奇数なので base × fastPow(base, exp-1)
fastPow(0.5, 0) = 1 (ベースケース)
= 0.5 × 1 = 0.5
= 0.5 × 0.5 = 0.25
最終結果: 2^-2 = 0.25

🎮 インタラクティブデモ

独自の値でテストしてみましょう：

結果が表示されます
計算ステップが表示されます

🔍 奇数指数と負の指数の詳細解説

🔢 奇数指数の処理: x^n = x × x^(n-1)

なぜこの変換をするのか？

奇数の指数は2で割り切れないため、直接半分にできません。そこで「1つ分を取り出して」偶数にします。

数学的根拠

x^5 = x × x^4
x^7 = x × x^6
x^9 = x × x^8

アルゴリズム的利点

n-1 は必ず偶数になる
→ 次のステップで半分に分割可能

具体例

2^5 = 2 × 2^4
2^4 = (2^2)^2 = 4^2 = 16
結果: 2 × 16 = 32

// 奇数指数の例：2^5 の計算過程 function calculateOddExample() { // Step 1: 2^5 は奇数なので 2 × 2^4 に分解 let result = 2 * fastPow(2, 4); // Step 2: 2^4 は偶数なので (2^2)^2 に分解 let half = fastPow(2, 2); // = 4 let pow4 = half * half; // = 4 × 4 = 16 // Step 3: 最終結果 return 2 * 16; // = 32 }

➖ 負の指数の処理: x^(-n) = (1/x)^n

数学的根拠

負の指数は「逆数の正の指数」として計算できます。

数学的定義

x^(-n) = 1 / x^n
= (1/x)^n

変換例

2^(-3) = 1 / 2^3
= (1/2)^3
= 0.5^3

アルゴリズム的利点

負の指数を正に変換
→ 同じロジックで処理可能

// 負の指数の例：2^(-3) の計算過程 function calculateNegativeExample() { // Step 1: 負の指数を検出 let x = 2, n = -3; // Step 2: x を 1/x に変換、n を正数に変換 x = 1 / x; // x = 1/2 = 0.5 n = -n; // n = 3 // Step 3: 通常の正の指数として計算 return fastPow(0.5, 3); // = 0.125 }

🔄 なぜ x^(n-1) でなく、直接 x^(n/2) を使わないのか？

❌ 間違った方法：奇数を強制的に半分にする

// 間違い：奇数指数を強制的に半分にしようとする if (exp % 2 === 1) { let half = fastPow(base, exp / 2); // ❌ 5/2 = 2.5 (小数) return half * half; // ❌ 結果が不正確 }

✅ 正しい方法：1つを取り出して偶数にする

// 正解：奇数指数から1を引いて偶数にする if (exp % 2 === 1) { return base * fastPow(base, exp - 1); // ✅ exp-1は必ず偶数 }

🎯 実際の計算比較

比較結果が表示されます