計算量(オーダー)の比較ツール

正解：C. O(n²)

比べる組の数は (n−1) + (n−2) + … + 1 = n(n−1)/2 で、n = 10 なら45回、n = 1000 なら499,500回です。計算量のオーダーは n が大きくなったときの増え方だけを見るので、係数の1/2や低い次数の項を省いて O(n²) と表します。n が2倍になると回数はおよそ4倍になります。O(n) は全要素を1回ずつ見るだけの処理、O(n log n) はマージソートのように半分に分けることを繰り返す処理の計算量です。

正解：B. 8秒

O(n²) では処理時間がデータ数の2乗に比例するので、データ数が4倍になると処理時間は 4² = 16倍になり、0.5秒 × 16 = 8秒です。2秒はデータ数に比例する O(n) の場合、32秒は3乗に比例する O(n³) の場合(4³ = 64倍)の値です。実際には、データがキャッシュに入りきらなくなるなどの影響で、これより遅くなることもあります。

正解：B. 50.5回

目的の値が k 番目にあれば比較は k 回なので、平均は (1 + 2 + … + 100) / 100 = 50.5回、一般には (n + 1)/2 回です。最良の場合(先頭にある)は1回、最悪の場合(末尾にある)は100回で、平均も最悪も n に比例するので計算量は O(n) です。約7回は log₂ 100 ≈ 6.6 に当たる二分探索の回数で、データが整列されていなければ使えません。

正解：A. 10回

1回の比較で探す範囲がほぼ半分になり、2¹⁰ = 1024 ≥ 1000 なので、最大でも10回で範囲がなくなります(⌊log₂ 1000⌋ + 1 = 10)。計算量は O(log n) で、100万個でも最大20回で済みます。32回は √1000 ≈ 31.6 に当たる値で、500回は線形探索の平均(約 n/2)に近い値です。ただし、二分探索を使うにはデータが整列されている必要があり、整列にかかる O(n log n) の手間も考える必要があります。