累乗を求める再帰的プログラムの乗算回数のプログラム計算量を調べる
最近すっかり忘れてたので、自分用に簡単にメモ
Javaで累乗を求める場合、Mathクラスのpow関数を呼び出せば簡単に求めることが出来るが、今回はプログラム計算量の求め方も書くので使わない。
ちなみに呼び出し方は
Math.pow(x, n)
x^nの再帰的プログラムは下のように書ける
power.java今回は乗算回数のプログラム計算量を求めるので、赤文字で書かれたところが実行されると回数に１を加えていくことになる。class power {
int power(int x, int n) {
int t;if(n == 1) {
return x;
}
t = power(x, n / 2);
if(n % 2 == 0) {
return t * t;
}else{
return t * t * x;
}
}
}
3^1の場合
return 33^2の場合
回数：0
t = power(3, 1) = 33^3の場合
return 3 * 3 = 9
回数：１
t = power(3, 1) = 33^4の場合
return 3 * 3 * 3 = 27
回数：１
t = power(3, 2) = 93^5の場合
return 9 * 9 = 81
回数：2
t = power(3, 2) = 93^6の場合
return 9 * 9 * 3 = 243
回数：2
t = power(3, 3) = 273^7の場合
return 27 * 27 = 729
回数：2
t = power(3, 3) = 273^8の場合
return 27 * 27 * 3 = 2187
回数：2
t = power(3, 4) = 813^9の場合
return 81 * 81 = 6561
回数：3
t = power(3, 4) = 813^10の場合
return 81 * 81 * 3 = 19683
回数：3
t = power(3, 5) = 2433^16の場合
return 243 * 243 = 59049
回数：3
t = power(3, 8) = 6561
return 6561 * 6561 = 43046721
回数：4
log nの値は下のようになるで、回数と比較していく
log 2 = log(2^1) = 1
log 4 = log(2^2) = 2
log 8 = log(2^3) = 3
log 16 = log(2^4) = 4
小数点以下は切り捨てるので今回のプログラム計算量はO(log n)と分かる。
プログラムを実行させるには下みたいなコードを書けばいい。今回は頭の中で回数は数えたが、数えきれない場合はpowerクラスのreturnの前でカウントを行えばいい。
testpowerclass testpower {
public static void main(String[] args) {
int x = Integer.parseInt(args[0]);
int n = Integer.parseInt(args[1]);
int result = 0;power p1 = new power();
result = p1.power(x, n);
System.out.println(result);
}
}【実行結果】
java ****$ javac testpower.java
java****$ java testpower 3 3
27
