平成29年度 春期 午前Ⅱ 問19

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

解説

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

入れ子ループ法は、一方の表の行を一つずつ取り出し、そのたびにもう一方の表の行を全部たどって、結合条件に合う組を探す方法です。見分ける軸は、比較の回数がnにどう比例して増えるかです。外側の表の行がn個あり、その1行ごとに内側の表のn行と比べるので、比較の回数はn×n＝n^2回です。たとえばnが10倍になると、比較の回数は100倍になります。この増え方を計算量の記法で表すとO(n^2)です。ループを入れ子にした処理は、ループの回数どうしを掛け合わせて見積もる、と覚えておくと計算量を素早く判断できます。

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

• アO(2n)：O(2n)は、表を2回走査する程度の手間を表しますが、定数倍を除けばO(n)と同じ大きさです。外側の各行ごとに内側を全部たどる入れ子ループ法では、回数がnの2乗で増えます。
• イO(log n)：O(log n)は、索引をたどって一つの値を探すときのように、nが増えてもごくゆっくりしか増えない手間です。二つの表の全行の組合せを比べる結合の手間はこれよりずっと大きくなります。
• エO(n log n)：O(n log n)は、整列のように、分割を繰り返して処理する方法で現れる大きさです。入れ子ループ法は整列を使わず、外側の各行ごとに内側の全行と比べるので、これより大きくなります。