データベーススペシャリスト試験 令和3年度 秋期 午前II 問15

【正解】エ

単純な入れ子ループ法では、一方の表を外側表、もう一方の表を内側表として処理します。外側表からタプルを1件取り出すたびに、結合条件に一致するタプルを探すため、内側表の全タプルを順に調べます。両方の表のタプル数がnなので、外側表の走査回数はn回であり、その1回ごとに内側表をn件比較します。したがって、比較回数はn×n＝n²となり、定数倍や低次の項を無視した計算量はO（n²）です。例えば、各表が100件なら、最大で100×100＝10,000組を比較します。

アのO（log n）は誤りです。これは、探索範囲を半分ずつ狭める二分探索や、平衡木索引を利用した探索などで現れる計算量です。単純な入れ子ループ法の全組合せ比較には当てはまりません。

イのO（n）は誤りです。これは表を1回だけ走査する処理や、適切なハッシュ表を利用できる場合の平均的な処理などの計算量です。内側表をn回走査する本問とは異なります。

ウのO（n log n）は誤りです。これは一般的な効率のよいソートや、ソートを前処理に使う結合などで現れます。単純な入れ子ループ法の計算量ではありません。

【ポイント】 入れ子ループ法は「外側の件数×内側の件数」で考えます。件数がm件とn件ならO（mn）です。 索引を利用する索引付き入れ子ループ法では、内側表の探索コストが下がり、単純なO（n²）とは異なる場合があります。