平成31年度 春期 午前Ⅱ 問16

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

解説

一方の各行ごとに他方の全行を調べるので、n×nでO(n^2)です。

入れ子ループ法は、一方の表から1行取り出すたびに、もう一方の表の行を先頭から全て調べて結合条件に合うものを探す方法です。外側の表にn行、内側の表にn行あれば、比較の回数はn×n＝n^2回になります。表の大きさが2倍になると比較の回数は4倍に増えるので、計算量はO(n^2)と表せます。索引も整列も使わずに、二重の繰返しで全ての組合せを調べるという仕組みから計算量を組み立てると、選択肢を見分けられます。

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

• アO(n)：O(n)は、各行を一度ずつ見るだけで済む処理の計算量です。入れ子ループ法では外側の1行ごとに内側の全行を見るので、行数に比例する回数では済みません。
• イO(log n)：O(log n)は、整列済みのデータを二分探索するように、調べる範囲を毎回半分に絞れる処理の計算量です。全ての組合せを順に調べる入れ子ループ法とは、仕組みがまったく違います。
• エO(n log n)：O(n log n)は、両方の表を結合に使う列で整列してから突き合わせる方法などで現れる計算量で、整列にかかる手間がこの形になります。整列をせずに全組合せを調べる入れ子ループ法には当たりません。