c - O（log n）でx^yを計算します

Question

インタビューの質問：

O（log n）でx^yを計算します

「IndianPowerアルゴリズムを使用する」や

double power(double x, int y) 
{
    if(y == 0) return 1;

    double d = power(x, y/2);

    if(y%2 == 0) return d*d;
    else return x*d*d;
}

1. 正解ですか？

2. この質問のコードを書くためのより良い方法はありますか？

Answer 1

これは、二乗による指数化と呼ばれます。実装に関する限り、それは好みの問題です。あなたの再帰的実装は良いですが、非再帰的実装（上記のリンクから）は、再帰が好きではない人や、それがどういうわけか「無駄」または「遅い」と誤って信じている人には少しきれいに見えるかもしれません。

Answer 2

基本的な数学演算に関する質問、および計算の複雑さに関する質問は、通常、ウィキペディアによって迅速に回答されます。

べき乗：積分パワーの効率的な計算

一般に、bnの計算に必要な乗算演算の数は、2乗による指数または（より一般的には）加算チェーンの指数を使用することにより、Θ（log n）に減らすことができます。乗算の最小シーケンス（指数の最小長の加算チェーン）を見つけることは、現在効率的なアルゴリズムが知られていない難しい問題ですが（サブセット和問題を参照）、かなり効率的なヒューリスティックアルゴリズムが多数利用できます。

Answer 3

それを分析しましょう：

poweryは、元の値が2で割り切れる回数（再帰を介して）と呼ばれます（つまり、の最大数、、kなど2^k < y）。これは、計算の数がおおよそk=log_2(2^k)=log_2(y)~=log(y)であるということを意味するので、それは正解です。

「より良い方法」への答えは、何が「より良い」と見なされるかによって異なります

Answer 4

これを行う方法は次のとおりです。

あなたが2^1024にしたいとしましょう、それはかかるでしょう...それを待つ...11回の乗算

あなたはこのようにします

2*2 = 2^2
2^2 * 2^2 = 2^4
2^4 * 2^4 = 2^8
2^8 * 2^8 = 2^16
....
2^512 * 2^512 = 2^1024

したがって、基本的には、指数を基数2で記述し、関連するすべての乗算を取得するだけで済みます。

Answer 5

これははるかに高速です。%これは非常にコストのかかる操作です。ビット単位の操作に置き換えると、大幅な節約になります。y/2また、に置き換えy>>1ます：

double power(double x, int y) {
    if(y == 0) return 1;

    double d = power(x, y>>1);

    if((y&1) == 0) return d*d;
    else return x*d*d;
}