平成27年度 春期 データベーススペシャリスト試験 午前Ⅱ 問17
テクノロジ／データベース関係データベースにおいて，タプル数nの表二つに対する結合操作を，入れ子ループ法によって実行する場合の計算量はどれか。
出典：平成27年度 春期 データベーススペシャリスト試験 午前Ⅱ 問17
- アO(2n)
- イO(log n)
- ウO(n²)
- エO(n log n)
正解：ウ
解説
入れ子ループ法（ネステッドループ結合）は，一方の表（外側の表）の各行に対して，もう一方の表（内側の表）の全行を走査し，結合条件を満たすかどうかを判定する方式である。タプル数nの表二つを結合する場合，外側の表のn行それぞれについて内側の表のn行を走査するため，比較回数はおよそn×n＝n²となり，計算量はO(n²)になる。
選択肢ごとの解説
- ア誤り。O(2n)は，結合対象の二つの表をそれぞれ1回ずつ走査する程度の計算量であり，入れ子ループ法のように一方の表の各行に対してもう一方の表を全走査する処理の計算量としては小さすぎる。
- イ誤り。O(log n)は，2分探索や平衡木の探索など，対数的な計算量をもつ処理に対応するものであり，全行同士を総当たりで比較する入れ子ループ法の計算量ではない。
- ウ正しい。入れ子ループ法では，外側の表のn行それぞれに対して内側の表のn行を走査するため，比較回数はn×n＝n²となり，計算量はO(n²)である。
- エ誤り。O(n log n)は，ソートを伴う処理（例えばソートマージ法）などに近い計算量であり，全行同士を総当たりで比較する入れ子ループ法の計算量とは異なる。