整数ベースのべき関数を実装するための最も効率的な方法
1. 概要
このチュートリアルでは、整数ベースのべき関数を実装するための最も効率的な方法について説明します。
まず、問題を定義します。 次に、それを説明するための例を示します。
次に、この問題を解決するための2つの異なるアプローチを紹介します。
2. 問題の定義
2つの正の整数とが与えられた場合、を計算する必要があります。
次の例を見てみましょう。
- , .
- , .
- , .
それ自体に時間を掛けたものに等しいことを思い出してください。
3. ループアプローチ
3.1. 本旨
問題を解決するために、forループを使用して時間を乗算します。
3.2. アルゴリズム
実装を見てみましょう：
まず、答えを格納する変数として宣言し、その初期値はに等しくなります。 1から始める理由は、ゼロの累乗の任意の数が1に等しいためです。 次に、反復を含むforループを開始し、各反復で現在のを乗算します。
結局、はに等しくなります。
3.3. 複雑さ
このアルゴリズムの複雑さはです。ここで、は問題の指数部分です。 この複雑さの背後にある理由は、操作を行うためにループを使用しているためです。
4. 高速電力アプローチ
4.1. 本旨
このアプローチでは、電力プロパティの1つを使用します。 R ecallはと同じです。 したがって、毎回、現在のベースを2乗し、電力を2で割ることができます。 処理するケースは2つあります。
- 指数部分が偶数の場合、はに等しくなります。
- 一方、が奇数の場合、はに等しくなります。
最後に、パワーがゼロに等しくなると、結果は問題の答えに等しくなります。
4.2. アルゴリズム
実装を見てみましょう：
最初に、回答を格納する変数として宣言します。 ゼロの累乗の数値は1に等しいため、初期値をに設定します。 次に、パワーがゼロより大きい限り、パワーが奇数かどうかをチェックします。 その場合、をベースで乗算し、パワーを1つ減らします。
このステップの後、値は偶数になります。 したがって、パワーを2で割り、ベースを2乗します。 電力がゼロになるまで、このプロセスを繰り返します。
最後に、に等しいを返します。
4.3. 複雑さ
このアルゴリズムの複雑さはです。ここで、は指数部分です。
この複雑さの背後にある理由は、各反復でパワーを2で割ることです。 したがって、全体として、ループ内に反復があります。
5. 結論
この記事では、整数ベースのべき関数を実装するための最も効率的な方法を紹介しました。
まず、問題を説明する例を示しました。 次に、それを解決するための2つの異なるアプローチを示し、それらの実装について説明しました。
