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

【解説】

入れ子ループ法の計算量
入れ子ループ法（Nested Loop Join）は、以下の手順で結合操作を行います：

1. 一つの表の各タプルについて、もう一つの表の全てのタプルを走査し、条件を満たすかを確認します。
2. この操作を全てのタプルに対して繰り返します。

このアルゴリズムの計算量を考えると、以下のようになります：

• 一つの表に n タプル、もう一つの表にも n タプルがある場合、外側のループは n 回、内側のループも n 回実行されます。
• 結果として、計算量は O(n × n) = O(n²) となります。

各選択肢の検討

ア: O(2n)
誤り。O(2n) は単純な線形計算を示すもので、入れ子ループ法の計算量には該当しません。

イ: O(log n)
誤り。O(log n) は主に木構造やバイナリ検索で発生する計算量です。入れ子ループ法には該当しません。

ウ: O(n²)
正しい。入れ子ループ法では外側と内側のループがネストされているため、計算量は O(n²) です。

エ: O(n log n)
誤り。O(n log n) はマージソートやヒープソートのようなアルゴリズムに関連する計算量であり、入れ子ループ法の計算量ではありません。