平成31年度 春期 データベーススペシャリスト試験 午前Ⅱ 問16
テクノロジ／データベース関係データベースにおいて，タプル数nの表二つに対する結合操作を，入れ子ループ法によって実行する場合の計算量はどれか。
出典：平成31年度 春期 データベーススペシャリスト試験 午前Ⅱ 問16
- アO(n)
- イO(log n)
- ウO(n²)
- エO(n log n)
正解：ウ
解説
入れ子ループ法は，一方の表（外側表，タプル数n）の各タプルについて，もう一方の表（内側表，タプル数n）を先頭から末尾まで走査して結合条件に合致するタプルを探す方法です。外側のn件それぞれに対して内側のn件を走査するため，比較回数はn×nに比例し，計算量はO(n²)になります。
選択肢ごとの解説
- ア誤り。O(n)は，例えば索引を使って1件ずつ直接該当行を求められるような場合の計算量であり，全件同士を突き合わせる入れ子ループ法の計算量ではありません。
- イ誤り。O(log n)は，B木索引などを使って二分探索的に絞り込む場合の計算量であり，全表走査を繰り返す入れ子ループ法の計算量ではありません。
- ウ正しい。入れ子ループ法では，外側表のn件それぞれについて内側表のn件を走査するため，比較回数はn×nに比例し，計算量はO(n²)になります。
- エ誤り。O(n log n)は，マージジョイン法のようにあらかじめソートを行ってから結合する場合などに近い計算量であり，単純な入れ子ループ法の計算量ではありません。