平成24年度 春期 午前Ⅱ 問18

✓ これが正解ウn^2

解説

一方の n 行それぞれについて他方の n 行を調べるので、n^2 です。

入れ子ループ法は、外側の表の1行ごとに内側の表の全行を順に調べ、結合条件を満たす組を探す方法です。外側の表のタプル数が n、内側の表のタプル数も n なので、比較の回数は n×n＝n^2 回になります。たとえば n＝1,000 なら比較は100万回で、表が大きくなると急激に増えます。索引を使ったり、両方の表をあらかじめ並べ替えてから突き合わせたりする方法では、この比較の回数を減らせます。結合の計算量は、二重のループで全組合せを調べるなら n^2、と形で覚えておくと判断できます。

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

• ア2n：2n は、二つの表をそれぞれ1回ずつ読むだけの場合の量です。入れ子ループ法は外側の1行ごとに内側を読み直すので、読み出しの回数は掛け算で増えます。
• イlog n：log n は、二分探索のように探索範囲を半分ずつに絞る場合の量です。入れ子ループ法は内側の表を全件調べるので、外側の一つの行に対してだけでも n に比例します。
• エn log n：n log n は、並べ替えてから突き合わせる方法などで現れる量です。入れ子ループ法は並べ替えを行わずに全組合せを調べるので、n^2 になります。