[leetcode] 50. Pow(x, n)の「二分累乗法の効率化」はなぜ速いのか
[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になります。このように、指数が大きくても
0