データ構造とアルゴリズム
計算量が O(n²) のプログラムで、データ数が1,000のときに処理時間が0.5秒だった。データ数を4,000にすると、処理時間はおよそ何秒になるか。
- A2秒
- B8秒
- C32秒
答えと解説を見る
正解：B. 8秒
O(n²) では処理時間がデータ数の2乗に比例するので、データ数が4倍になると処理時間は 4² = 16倍になり、0.5秒 × 16 = 8秒です。2秒はデータ数に比例する O(n) の場合、32秒は3乗に比例する O(n³) の場合(4³ = 64倍)の値です。実際には、データがキャッシュに入りきらなくなるなどの影響で、これより遅くなることもあります。
- A. データ数に比例する O(n) なら4倍の2秒ですが、O(n²) では2乗で効きます。
- B. 正しい。4倍のデータで 4² = 16倍になり、0.5 × 16 = 8秒です。
- C. 4³ = 64倍とした O(n³) の場合の値です。