令和3年度 秋期 午前Ⅱ 問15

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

解説

外側 n 件ごとに内側 n 件を全て調べるので、計算量は O(n^2) です。

入れ子ループ法は、一方の表の各タプルについて、もう一方の表の全タプルを順に調べて、結合条件に合うものを探す方法です。外側の表に n 個のタプルがあり、その一つごとに内側の表の n 個を全て調べるので、比較の回数は n×n＝n^2 回になります。索引のような補助を使わないこの単純な形では、表の大きさが2倍になると比較回数は4倍に増えます。したがって計算量は O(n^2) です。二重のループで全ての組合せを調べると考えれば、二つの表の大きさを掛け合わせた回数になることがすぐに導けます。

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

• アO(log n)：O(log n) は、整列済みのデータを二分探索で一つ探すときのように、調べる範囲を毎回半分にできる場合の計算量です。全ての組合せを調べる入れ子ループ法では、タプルを一つずつ全部見るので、これほど少なくはなりません。
• イO(n)：O(n) は、表を1回だけ先頭から終わりまで読む処理の計算量です。入れ子ループ法では外側のタプル一つごとに内側の表を全て読み直すので、読む回数がさらに n 倍になります。
• ウO(n log n)：O(n log n) は、両方の表を整列してから突き合わせるような方法で見られる計算量です。整列を使わず、全ての組を順に比べる入れ子ループ法は、これより多くの比較を必要とします。