平成27年度 春期 午前Ⅱ 問17

✓ これが正解ウO(n^2)

解説

外側のn行ごとに内側のn行を調べるので、n×nでO(n^2)です。

入れ子ループ法は、一方の表の各行について、もう一方の表の全行を順に調べて、結合条件に合う組を探す方法です。外側の表にn行、内側の表にn行あれば、比較の回数は外側の1行につきn回、それがn行分なので、n×n＝n^2回になります。計算量は、データ量が増えたときに処理量がどの程度の割合で増えるかを表すもので、この場合は行数が2倍になると比較の回数は4倍になります。したがってO(n^2)です。ループが二重になっていればnの2乗、と構造から読み取るのが確実な方法です。

ほかの選択肢はなぜ違うのか

• アO(2n)：O(2n)は、二つの表をそれぞれ1回ずつ読むだけで済む場合の大きさで、定数倍を除けばnに比例する量です。入れ子ループ法では外側の1行ごとに内側を読み直すので、この大きさには収まりません。
• イO(log n)：O(log n)は、整列済みのデータを半分ずつ絞り込んで1件を探すときのような、ごく緩やかに増える大きさです。表の全行どうしを組み合わせて調べる結合処理は、これよりはるかに大きくなります。
• エO(n log n)：O(n log n)は、データを整列するときに現れる大きさです。入れ子ループ法は整列を使わず、外側の行ごとに内側の全行をたどるので、比較の回数はn^2の大きさになります。