x を n 乗するべき乗関数 power(x, n)をＣ言語で実装したい。べき乗を分解して、Ｏ(n)の計算量を Ｏ(log2(n))まで削減する実装として空欄 に入る最も適切なものはどれか。
ただし、n は0以上の整数とする。
double power(double x, int n) {
if (n == 0) return 1;
}
① int i;
double rv = x;
for (i = 1; i < n; i += 1) rv *= x;
return rv;
② if n % 2 == 0: return power(x * x, n / 2)
return x * power(x, n - 1)
③ if n % 2 == 0: return power(x * x, n / 2);
return x * power(x, n - 1);
④ if (n == 1) return x;
return x * power(x, n - 1);
⑤ if (n == 1) return x;
return x * power(x, n / 2);
③
計算量は、コンピュータが処理する速さの目安のことである。
n = 8のとき、8回ぐらい計算するのなら 計算量は Ｏ(ｎ)である。
n = 8のとき、3回 (=log28) ぐらい、n = 16のとき4回 (=log216) ぐらい計算するのなら、計算量は Ｏ(log2ｎ)である。
選択肢それぞれについて、n = 8の時に何回計算するかを調べる。
① for (i = 1; i < 8; i += 1) だから8回ループする。
1回目 x = x * x
2回目 x = x2 * x2 = x4
3回目 x = x4 * x4 = x8
4回目 x = x8 * x8 = x16
・・・
8回目 x = x256
で、x の n 乗が計算できない。
② ③と同じアルゴリズムだが、; が欠落しており、構文エラーである。
③ power(x, 8) = power(x*x, 4) = power(x*x * x*x, 2)
= power(x*x * x*x * x*x * x*x, 1) = power(x8, 1)
= x8 * power( x8, 0) = x8 * 1
となり、return の時に計算する数が4回となるので、正しい。
④ power(x, 8) = x * power(x, 7) = x*x * power(x, 6)
= x*x*x * power(x, 5) = ・・・ = x*x*x*x*x*x*x * power(x, 1)
= x*x*x*x*x*x*x * x
で、return の時に計算する数が8回となり、計算量はＯ(ｎ)である。
⑤ power(x, 8) = x * power(x, 4) = x * (x * power(x, 2))
= x * (x * (x * power(x, 1)))= x * (x * (x * x))
で、x の n 乗が計算できない。
| Ⅲ－２ | 目次 | Ⅲ－４ |