令和3年度 秋期 データベーススペシャリスト試験 午前Ⅱ 問15
テクノロジ／データベース関係データベースにおいて，タプル数 n の表二つに対する結合操作を，入れ子ループ法によって実行する場合の計算量はどれか。
出典：令和3年度 秋期 データベーススペシャリスト試験 午前Ⅱ 問15
- アO(log n)
- イO(n)
- ウO(n log n)
- エO(n²)
正解：エ
解説
入れ子ループ法（Nested Loop Join）は，一方の表の各タプルに対して，もう一方の表の全タプルを走査して結合条件を確認する方式です。両方の表がそれぞれn件のタプルをもつとすると，比較回数はおよそn×n回となるため，計算量はO(n²)です。
選択肢ごとの解説
- ア誤り。O(log n)は，例えば索引を使った探索など対数オーダーの処理を表すものであり，全件走査を伴う入れ子ループ法の結合の計算量ではありません。
- イ誤り。O(n)は線形の計算量であり，一方の表を1回走査するだけの処理を表しますが，入れ子ループ法では外側のループの1件ごとに内側の表を毎回全走査するため，これでは済みません。
- ウ誤り。O(n log n)は，例えばソートを利用したマージ結合など，整列を伴う結合アルゴリズムの計算量に相当し，単純な入れ子ループ法の計算量ではありません。
- エ正しい。入れ子ループ法では，外側の表のn件それぞれに対し内側の表のn件全てを走査して比較するため，計算量はO(n²)になります。