基本情報技術者 基礎理論 択一式（応用） 第66問〜第70問｜アルゴリズムとプログラミング

正解：A

・A
正解。nが10倍になるとAは10倍、Bは10の2乗＝100倍になる。したがってBの処理時間はAの100÷10＝10倍となる。

・B
20倍は、増加の倍率を単純に足し合わせた誤りである。

・C
100倍は、アルゴリズムBの処理時間の増加倍率そのものである。

・D
1000倍は、nの3乗に比例する場合の増加倍率である。

正解：C

・A
nは、単一のループを1回実行した場合の回数である。

・B
2nは、2つのループを入れ子ではなく並列に実行した場合の回数である。

・C
正解。外側のn回それぞれについて内側がn回実行されるため、n×n＝nの2乗回となる。二重ループは処理時間が件数の2乗に比例する典型例である。

・D
2のn乗は、部分集合を全て列挙する場合などの回数であり、二重ループの回数ではない。

正解：A

・A
正解。観測範囲では、データ件数が4倍になったときに処理時間も4倍になっているため、提示された選択肢の中では件数に比例する関係が最も適切である。ただし、二つの測定点だけで一般的な漸近計算量を証明できるわけではない。

・B
件数の2乗に比例するなら、件数が4倍になったとき処理時間は16倍になると予想され、この観測結果とは一致しない。

・C
対数に比例する場合、件数が4倍になっても処理時間は4倍にはなりにくく、この観測結果とは一致しない。

・D
件数に関係なく一定なら、処理時間は2秒のままであり、この観測結果とは一致しない。

正解：C

・A
10は深さの2倍を求めた誤りである。

・B
16は深さ4の階層にある節の数である。

・C
正解。根を深さ0とすると、各階層の節数は直前の階層の2倍になる。深さ5の葉の数は2の5乗＝32個である。

・D
64は深さ6の階層にある節の数である。

正解：D

・A
nに比例するのは、先頭から順に調べる線形探索の計算量である。

・B
nの2乗に比例するのは、バブルソートなどの単純な整列アルゴリズムの計算量である。

・C
2のn乗に比例するのは、全ての組合せを調べ尽くすような処理の計算量である。

・D
正解。2分探索は1回の比較で範囲が半分になるため、比較回数はnの対数に比例する。件数が大きくなっても比較回数の増え方は緩やかである。