データベーススペシャリスト 2017年午前2 問19

問題文

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

選択肢

ア：

O (2 n)

イ：

O (lo g n)

ウ：

O (n^{2})

（正解）

エ：

O (n lo g n)

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

要点まとめ

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

正解の理由

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

n

回、内側のループも

n

回繰り返されるため、計算量は

O (n \times n) = O (n^{2})

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

O (n^{2})

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

よくある誤解

入れ子ループ法は単純なため計算量が小さいと誤解されがちですが、実際は二重ループのため大きな計算量がかかります。
また、

O (lo g n)

や

O (n lo g n)

はソートやインデックスを利用した場合の計算量であり、入れ子ループ法には該当しません。

解法ステップ

入れ子ループ法の処理内容を理解する（外側ループと内側ループの二重ループ）。
各ループの繰り返し回数を確認する（それぞれ $n$ 回）。
全体の計算量は二重ループの積である $n \times n = n^{2}$ と判断する。
選択肢の中から $O (n^{2})$ に該当するものを選ぶ。

選択肢別の誤答解説

ア: $O (2 n)$
これは線形計算量であり、入れ子ループ法の二重ループ構造を反映していません。
イ: $O (lo g n)$
対数計算量は二分探索などで見られ、入れ子ループ法の全探索とは異なります。
ウ: $O (n^{2})$
正解。二重ループによる全探索の計算量を正しく表しています。
エ: $O (n lo g n)$
ソートや効率的な結合アルゴリズムで見られる計算量であり、単純な入れ子ループ法には該当しません。

補足コラム

関係データベースの結合操作には、入れ子ループ法以外にもソートマージ結合やハッシュ結合など効率的なアルゴリズムがあります。
これらは計算量を

O (n lo g n)

や

O (n)

に抑えることが可能で、大規模データの処理に適しています。
入れ子ループ法は実装が簡単ですが、データ量が増えると計算時間が急激に増加するため注意が必要です。

FAQ

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

Q: 計算量

O (n^{2})

はどのくらい遅いですか？
A: データ量が2倍になると処理時間は約4倍になるため、大量データでは非常に遅くなります。

Q: 他に効率的な結合方法はありますか？
A: はい。ソートマージ結合やハッシュ結合は計算量を大幅に削減できます。

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

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

このサイトについてプライバシーポリシー利用規約特商法表記開発者について

データベーススペシャリスト 2017年 午前2 問19

問題文

選択肢