データベーススペシャリスト 2015年 午前2 問17

関係データベースにおける入れ子ループ結合の計算量【午前2 解説】

要点まとめ

• 結論：入れ子ループ法による結合操作の計算量は $O(n^2)$ です。
• 根拠：表二つのタプル数がそれぞれ $n$ の場合、外側ループで $n$ 回、内側ループで $n$ 回の比較が必要になるためです。
• 差がつくポイント：結合アルゴリズムの計算量の違いを理解し、特に入れ子ループ法の非効率さを押さえることが重要です。

正解の理由

よくある誤解

解法ステップ

1. 入れ子ループ法の動作をイメージする（外側ループと内側ループの二重ループ）。
2. 外側の表のタプル数を $n$ とし、内側の表のタプル数も $n$ と設定。
3. 外側ループは $n$ 回繰り返し、内側ループも $n$ 回繰り返すため、比較回数は $n\times n=n^2$。
4. よって計算量は $O(n^2)$ と判断する。
5. 選択肢の中から $O(n^2)$ を示すものを選ぶ。

選択肢別の誤答解説

• ア: $O(2n)$
  → $2n$ は $O(n)$ と同義であり、入れ子ループ法の二重ループ構造を考慮していません。
• イ: $O(\log n)$
  → ログ計算量は主に二分探索やインデックス検索に関連し、入れ子ループ法には該当しません。
• ウ: $O(n^2)$
  → 正解。二重ループのため計算量は二乗オーダーです。
• エ: $O(n\log n)$
  → ソートやマージソートの計算量であり、入れ子ループ法の結合には適用されません。

補足コラム

FAQ