平成29年度 春期 データベーススペシャリスト試験 午前Ⅱ 問19
テクノロジ／データベース関係データベースにおいて，タプル数nの表二つに対する結合操作を，入れ子ループ法によって実行する場合の計算量はどれか。
出典：平成29年度 春期 データベーススペシャリスト試験 午前Ⅱ 問19
- アO(2n)
- イO(log n)
- ウO(n²)
- エO(n log n)
正解：ウ
解説
入れ子ループ法（ネステッドループ結合）は，外側の表の各タプルに対して，内側の表の全タプルを走査して結合条件を確認する方式です。タプル数nの表二つを結合する場合，外側のn個のタプルそれぞれについて内側のn個のタプルを走査するため，比較回数はn×n＝n²のオーダーになります。
選択肢ごとの解説
- ア誤り。O(2n)は，二つの表をそれぞれ1回ずつ，合計2n回程度走査するような線形の処理量に相当し，全組合せを突き合わせる入れ子ループ法の計算量としては小さすぎます。
- イ誤り。O(log n)は，例えば整列された表に対する2分探索など，探索を利用したアルゴリズムの計算量に相当し，全組合せを総当たりで確認する入れ子ループ法の計算量ではありません。
- ウ正しい。外側の表のn個のタプルそれぞれについて，内側の表のn個のタプルを走査して結合条件を確認するため，計算量はn×n＝O(n²)になります。
- エ誤り。O(n log n)は，例えば表をあらかじめソートしてから結合するソートマージ結合など，効率化された結合アルゴリズムの計算量に相当し，単純な入れ子ループ法の計算量ではありません。