データベーススペシャリスト 2019年午前2 問16

問題文

関係データベースにおいて、タプル数nの表二つに対する結合操作を、入れ子ループ法によって実行する場合の計算量はどれか。

選択肢

ア：

O (2 n)

イ：

O (lo g n)

ウ：

O (n^{2})

（正解）

エ：

O (n lo g n)

関係データベースの結合操作における入れ子ループ法の計算量【午前2 解説】

要点まとめ

結論：入れ子ループ法による結合操作の計算量は $O (n^{2})$ です。
根拠：タプル数 $n$ の表二つをそれぞれ全探索するため、全組み合わせを比較する必要があります。
差がつくポイント：結合アルゴリズムの計算量の違いを理解し、特に入れ子ループ法の非効率さを把握することが重要です。

正解の理由

入れ子ループ法は、外側の表の各タプルに対して内側の表の全タプルを順に比較します。
表がそれぞれ

n

個のタプルを持つ場合、比較回数は

n \times n = n^{2}

となり、計算量は

O (n^{2})

です。
したがって、選択肢の中で

O (n^{2})

を示す「ウ」が正解です。

よくある誤解

入れ子ループ法は単純なアルゴリズムのため、計算量が

O (n)

や

O (lo g n)

と誤解されやすいです。
また、結合操作全体の効率化策を知らずに、常に高速だと考えるのも誤りです。

解法ステップ

入れ子ループ法の動作をイメージする（外側ループと内側ループの二重ループ）。
各表のタプル数を $n$ と設定し、比較回数を計算する。
比較回数が $n \times n = n^{2}$ となることを確認する。
選択肢の中から $O (n^{2})$ を選ぶ。

選択肢別の誤答解説

ア: $O (2 n)$
これは単純に2倍の線形時間を示すが、入れ子ループ法の二重ループ構造を考慮していません。
イ: $O (lo g n)$
対数時間は二分探索などで見られますが、入れ子ループ法の結合には該当しません。
ウ: $O (n^{2})$
正解。二つの表の全組み合わせを比較するため、計算量は二乗になります。
エ: $O (n lo g n)$
ソートマージ結合などで見られる計算量ですが、入れ子ループ法には当てはまりません。

補足コラム

入れ子ループ法は実装が簡単で理解しやすい反面、大規模データには不向きです。
効率的な結合処理には、ソートマージ結合やハッシュ結合などのアルゴリズムが用いられ、これらは

O (n lo g n)

や

O (n)

に近い計算量を実現します。
試験対策では、各結合アルゴリズムの特徴と計算量を正確に覚えることが重要です。

FAQ

Q: 入れ子ループ法はどんな場合に使われますか？
A: 小規模データやインデックスがない場合に使われますが、大規模データには非効率です。

Q: ソートマージ結合と入れ子ループ法の違いは何ですか？
A: ソートマージ結合は両表をソートしてからマージするため

O (n lo g n)

の計算量で高速ですが、入れ子ループ法は単純に全組み合わせを比較し

O (n^{2})

となります。

関連キーワード: 関係データベース、結合操作、入れ子ループ法、計算量、アルゴリズム、データベース最適化

← 前の問題へ次の問題へ →

\ せっかくなら /

データベーススペシャリストを
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

データベーススペシャリスト 2019年 午前2 問16

問題文

選択肢