データベーススペシャリスト 2012年 午前2 問18

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

要点まとめ

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

正解の理由

よくある誤解

解法ステップ

1. 表のタプル数をそれぞれ $n$ と設定する。
2. 外側ループで表1の $n$ タプルを順に処理する。
3. 内側ループで表2の $n$ タプルを全て比較する。
4. 比較回数は $n\times n=n^2$ となることを確認する。
5. 選択肢の中から $n^2$ に該当するものを選ぶ。

選択肢別の誤答解説

• ア: $2n$
  単純に両表のタプル数を足しただけで、結合の比較回数を表していません。
• イ: $\log n$
  これは二分探索などの探索アルゴリズムの計算量であり、入れ子ループ法には当てはまりません。
• ウ: $n^2$
  正解。入れ子ループ法の計算量は二つの表のタプル数の積に比例します。
• エ: $n\log n$
  ソート結合など効率的な結合方法の計算量であり、単純な入れ子ループ法ではありません。

補足コラム

FAQ