平成24年度春期 データベーススペシャリスト 午前Ⅱ 問18

結合計算量を考える基本視点

関係データベースの結合を比較するときは、対象データの規模だけでなく、処理の進め方、利用できる構造、入出力の負担を分けて捉え、全体の増え方を段階的に確認しましょう。

この問題で問われていること

一つの観点として、結合処理がどのデータをどの順序で参照し、比較や探索の範囲をどう広げるかに注目し、規模が変わったときの負担の増え方と前提条件を整理しましょう。

視点

計算量を考える際は、操作名だけで判断せず、入力の大きさ、参照の単位、探索の繰り返し、準備や結果生成に伴う負担を分けて見ます。与えられた条件のどれが支配的かを整理し、比較の前提をそろえて考えましょう。

確認ポイント

• 入力データの規模として、どの対象の大きさが負担に影響するか。
• 処理の各段階で、参照や比較がどの範囲に及ぶか。
• 利用可能な準備情報や記憶装置への入出力を前提に含めるか。

正解

ウ

解説

二つの表の各タプルを入れ子ループで比較するため、外側の表のn件それぞれについて内側の表のn件を調べます。比較回数はn回×n回で、計算量はn²となります。

理由

外側のループは一方の表のn個のタプルについて反復し、各反復で内側のループがもう一方の表のn個のタプルを調べます。したがって比較回数は n回 × n回 = n²回となり、計算量はn²です。

比較

2nは二つの処理を単純に足し合わせる場合の増え方に近く、log nやn log nは探索や整列などで現れる代表的な計算量です。全組合せを比較する入れ子ループ法では、これらとは異なる増加になります。

選択肢ア

これは不正解だよ。2nは、二つの処理をそれぞれn回ずつ実行して合計するような場合の増え方です。この設問では、一方の表の各タプルについて、もう一方の表の全タプルを調べるため、処理は単純な足し算ではなく掛け算になります。

選択肢イ

これは不正解だよ。log nは、対象を段階的に絞り込む探索などで見られる増え方です。入れ子ループ法では、調査範囲を対数的に縮小する条件は示されておらず、各タプルに対して相手側のタプルを順に比較するため、この値にはなりません。

選択肢ウ（正解）

これは正解だよ。一方の表のn個のタプルを外側のループで処理し、その各回で他方の表のn個のタプルを内側のループで比較します。比較回数は n回 × n回 = n²回となるため、入れ子ループ法の計算量はn²です。

選択肢エ

これは不正解だよ。n log nは、n個の対象を処理しながら、各段階で探索範囲を対数的に扱うような場合の増え方です。この設問の入れ子ループでは、内側の処理がlog n回に抑えられる条件はなく、n回の比較が繰り返されます。

学習のポイント

入れ子ループの反復回数から計算量を見積もる方法を理解する。