平成29年度 春期 データベーススペシャリスト試験 午前II 問19

【解説】

入れ子ループ法（Nested Loop Join）の計算量
入れ子ループ法は、以下のように二つの表のタプルを結合するアルゴリズムです。

1. 外側の表の各タプルについてループを回す。
2. 各タプルごとに内側の表を全探索する。

このため、計算量は次のように求められます。

• 外側の表に n 個のタプルがあり、内側の表に n 個のタプルがある場合、結合操作に必要な計算量は n × n = n² です。

各選択肢の検討

ア: O(2n)
誤り。入れ子ループ法では、外側の表と内側の表を完全にループするため、線形計算量ではありません。

イ: O(log n)
誤り。二分探索などを伴う操作で見られる計算量ですが、入れ子ループ法には該当しません。

ウ: O(n²)
正しい。入れ子ループ法の計算量に該当します。

エ: O(n log n)
誤り。ソートやハッシュ結合などの効率的なアルゴリズムに該当する計算量ですが、入れ子ループ法ではありません。