解説

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

要点まとめ

• 結論：入れ子ループ法による2つの表の結合は計算量が$O(n^2)$となる。
• 根拠：外側のループで$n$回、内側のループでも$n$回の比較が必要なため、総計$n \times n = n^2$回の操作が発生する。
• 差がつくポイント：結合アルゴリズムの計算量を理解し、特に入れ子ループ法の非効率さを把握しているかが重要。

正解の理由

よくある誤解

解法ステップ

1. 入れ子ループ法の動作をイメージする（外側の表の各タプルに対し内側の表を全探索）。
2. 外側の表のタプル数を$n$、内側の表のタプル数も$n$と仮定する。
3. 外側ループで$n$回、内側ループで$n$回の比較が行われることを確認。
4. 総比較回数は$n \times n = n^2$となり、計算量は$O(n^2)$と判断。
5. 選択肢の中から$O(n^2)$を選ぶ。

選択肢別の誤答解説

• ア: $O(\log n)$
  → 二重ループの計算量を誤解。$O(\log n)$は二分探索などの計算量であり、入れ子ループ法には該当しない。
• イ: $O(n)$
  → 片方の表だけを走査する場合の計算量。入れ子ループ法は両方の表を全探索するため、これより大きい。
• ウ: $O(n \log n)$
  → ソートや効率的な結合アルゴリズムの計算量に近いが、単純な入れ子ループ法ではない。
• エ: $O(n^2)$
  → 入れ子ループ法の典型的な計算量で正解。

補足コラム

FAQ