データベーススペシャリスト試験 2019年 午前2 問16

解説

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

要点まとめ

• 結論：入れ子ループ法による結合操作の計算量は $O(n^2)$ です。
• 根拠：タプル数 $n$ の表二つをそれぞれ全探索するため、全組み合わせを比較する必要があります。
• 差がつくポイント：結合アルゴリズムの計算量の違いを理解し、特に入れ子ループ法の非効率さを把握することが重要です。

正解の理由

よくある誤解

解法ステップ

1. 入れ子ループ法の動作をイメージする（外側ループと内側ループの二重ループ）。
2. 各表のタプル数を $n$ と設定し、比較回数を計算する。
3. 比較回数が $n\times n=n^2$ となることを確認する。
4. 選択肢の中から $O(n^2)$ を選ぶ。

選択肢別の誤答解説

• ア: $O(2n)$
  これは単純に2倍の線形時間を示すが、入れ子ループ法の二重ループ構造を考慮していません。
• イ: $O(\log n)$
  対数時間は二分探索などで見られますが、入れ子ループ法の結合には該当しません。
• ウ: $O(n^2)$
  正解。二つの表の全組み合わせを比較するため、計算量は二乗になります。
• エ: $O(n\log n)$
  ソートマージ結合などで見られる計算量ですが、入れ子ループ法には当てはまりません。

補足コラム

FAQ