[leetcode] 50. Pow(x, n)の「二分累乗法の効率化」はなぜ速いのか
const myPow = function(x, n) {
function binaryExp(x, n){
if(n === 0) return 1;
if(n < 0) return 1 / binaryExp(x, -1 * n);
if(n % 2 === 1){
return x * binaryExp(x * x, (n - 1) / 2);
} else {
return binaryExp(x * x, n / 2);
}
}
return binaryExp(x, n)
};
このmyPow関数は、数値xをn乗した結果を効率的に計算するためのものです。これは「二分累乗法」という手法を使っています。
#### 基本ケース:
nが0の場合、どんな数でも0乗は1なので、1を返します。
nが負の場合、1 / binaryExp(x, -n)で計算します。これは正の指数で計算して、その結果を逆数にするためです。
#### 再帰的な計算:
nが奇数なら、x * binaryExp(x * x, (n - 1) / 2)で計算します。xを一度掛けてから、nを半分にします。
nが偶数なら、binaryExp(x * x, n / 2)で計算します。nを半分にして計算を続けます。
例:
myPow(2, 10)の場合、結果は1024になります。このように、指数が大きくても高速に計算できます。
### nが負の場合、1 / binaryExp(x, -n)で計算します。これは正の指数で計算して、その結果を逆数にするため？
nが負の場合、例えばx^-3のようなケースを考えてみましょう。
例としてmyPow(2, -3)を考えると：
#### 計算手順:
nが負なので、nを正にして計算します。この場合、n = -3が正の3に変わります。
まず、2^3を計算します。2^3 = 8ですね。
次に、その結果を逆数にします。1 / 8 = 0.125になります。
つまり、2^-3という計算は、「まず2を正の指数で計算し、その結果を逆数にする」という流れで行われます。
なぜこうするのか？
負の指数は数学的に「逆数を取る」という意味を持ちます。x^-nは1 / x^nと同じです。例えば2^-3は、1 / 2^3、すなわち1 / 8です。
このように、まず正の指数で普通に計算してから、その結果の逆数を取ることで、負の指数も正しく計算できます。
### なぜこの関数が速いのか
このmyPow関数が速い理由は、「二分累乗法」（Exponentiation by Squaring）を使っているからです。この方法では、計算の回数を大幅に減らすことができます。
#### 通常の計算方法との違い
通常、x^nを計算するには、xをn回掛け算します。例えば、2^10を計算する場合、2 * 2 * 2 * ... * 2を10回行います。これは大きな指数では非常に多くの掛け算が必要になります。
二分累乗法の効率化
二分累乗法では、以下のように計算を分割して進めます：
`nが偶数の場合：x^n = (x^2)^(n/2)`
`nが奇数の場合：x^n = x * (x^2)^((n-1)/2)`
この方法では、毎回指数を半分にして計算するため、掛け算の回数が大幅に減ります。
#### 具体例：2^10の場合
2^10は偶数なので、(2^2)^5、つまり4^5に変換します。
4^5は奇数なので、4 * (4^2)^2に変換し、次に16^2を計算します。
最終的に16^2 = 256なので、4 * 256 = 1024という結果が得られます。
これにより、10回の掛け算をする代わりに、わずか4回の掛け算で済むようになります。指数が大きくなるほど、この効率の差はさらに大きくなります。
