データベーススペシャリスト 2021年午前2 問15

問題文

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

選択肢

ア：

O (lo g n)

イ：

O (n)

ウ：

O (n lo g n)

エ：

O (n^{2})

（正解）

関係データベースの入れ子ループ結合の計算量【午前2 解説】

要点まとめ

結論：入れ子ループ法による2つの表の結合は計算量が $O (n^{2})$ となる。
根拠：外側のループで $n$ 回、内側のループでも $n$ 回の比較が必要なため、総計 $n \times n = n^{2}$ 回の操作が発生する。
差がつくポイント：結合アルゴリズムの計算量を理解し、特に入れ子ループ法の非効率さを把握しているかが重要。

正解の理由

入れ子ループ法は、外側の表の各タプルに対して内側の表の全タプルを順に比較する単純な結合方法です。
表のタプル数がそれぞれ

n

の場合、外側ループで

n

回、内側ループで

n

回の比較が行われるため、計算量は

O (n^{2})

となります。
このため、選択肢の中で

O (n^{2})

である「エ」が正解です。

よくある誤解

入れ子ループ法の計算量を

O (n)

や

O (n lo g n)

と誤認しやすいですが、単純な二重ループであるため二乗の計算量になります。
また、インデックスを利用した結合と混同してしまうことも多いです。

解法ステップ

入れ子ループ法の動作をイメージする（外側の表の各タプルに対し内側の表を全探索）。
外側の表のタプル数を $n$ 、内側の表のタプル数も $n$ と仮定する。
外側ループで $n$ 回、内側ループで $n$ 回の比較が行われることを確認。
総比較回数は $n \times n = n^{2}$ となり、計算量は $O (n^{2})$ と判断。
選択肢の中から $O (n^{2})$ を選ぶ。

選択肢別の誤答解説

ア: $O (lo g n)$
→ 二重ループの計算量を誤解。 $O (lo g n)$ は二分探索などの計算量であり、入れ子ループ法には該当しない。
イ: $O (n)$
→ 片方の表だけを走査する場合の計算量。入れ子ループ法は両方の表を全探索するため、これより大きい。
ウ: $O (n lo g n)$
→ ソートや効率的な結合アルゴリズムの計算量に近いが、単純な入れ子ループ法ではない。
エ: $O (n^{2})$
→ 入れ子ループ法の典型的な計算量で正解。

補足コラム

入れ子ループ法は最も単純な結合アルゴリズムですが、効率が悪いため大規模データには不向きです。
より効率的な結合方法としては、ソートマージ結合やハッシュ結合があり、これらは計算量を

O (n lo g n)

や

O (n)

に抑えられます。
また、インデックスを利用した結合も計算量削減に有効です。

FAQ

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

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

O (n lo g n)

程度で、入れ子ループ法より高速です。

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

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

データベーススペシャリスト 2021年 午前2 問15

問題文

選択肢