解説

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

要点まとめ

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

正解の理由

よくある誤解

解法ステップ

1. 入れ子ループ法の処理内容を理解する（外側ループと内側ループの二重ループ）。
2. 各ループの繰り返し回数を確認する（それぞれ $n$ 回）。
3. 全体の計算量は二重ループの積である $n \times n = n^2$ と判断する。
4. 選択肢の中から $O(n^2)$ に該当するものを選ぶ。

選択肢別の誤答解説

• ア: $O(2n)$
  これは線形計算量であり、入れ子ループ法の二重ループ構造を反映していません。
• イ: $O(\log n)$
  対数計算量は二分探索などで見られ、入れ子ループ法の全探索とは異なります。
• ウ: $O(n^2)$
  正解。二重ループによる全探索の計算量を正しく表しています。
• エ: $O(n \log n)$
  ソートや効率的な結合アルゴリズムで見られる計算量であり、単純な入れ子ループ法には該当しません。

補足コラム

FAQ