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

結合処理の計算量を考える視点

結合の計算量を検討するときは、処理対象の規模だけでなく、選ばれた手順が各段階でどの対象を何回参照する設計か、準備に何が含まれるかを分け、全体の負担を整理して考えます。

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

一つの観点として、結合に使う二つの対象について、外側と内側の扱い、参照の繰り返し、利用できる事前準備の有無を対応づけ、どの処理部分が全体の負担を左右するか確認しましょう。

視点

計算量を整理する際は、入力の大きさを一括して見るのではなく、処理の入れ子構造と、同じ対象への参照が繰り返されるかに注目します。さらに、比較前に用意された構造がある場合は、その準備と利用を分けて考えると、見積もりの前提を整理しやすくなります。

確認ポイント

• 二つの入力のうち、どちらが繰り返し参照される側として扱われているか
• 同じ対象への探索や比較が、処理の中で何度発生する設計になっているか
• 事前の整理や検索用構造の準備を、実行時の処理と分けて考えているか

正解

ウ

解説

入れ子ループ法による結合では、片方の表の各タプルに対して、もう片方の表の全タプルを調べます。したがって、nタプル同士では比較回数が n × n = n² 回となり、計算量は O(n²) です。

理由

外側のループが n タプル分、内側のループも n タプル分実行されるため、調査するタプル対の数は n × n = n² 回です。よって計算量は O(n²) になります。

比較

O(2n)やO(n log n)は、二つの表の全タプルの組合せを調べる入れ子ループの増え方を表していません。O(log n)も、入力を段階的に絞る処理の増え方であり、この結合方法には当てはまりません。

選択肢ア

これは不正解だよ。O(2n)は、nに比例する処理を定数回行う場合の増え方です。この方法では、外側のnタプルそれぞれについて内側のnタプルを調べるため、処理回数は2nではなく n×n = n² 回になります。

選択肢イ

これは不正解だよ。O(log n)は、入力規模が増えても処理範囲を段階的に絞るような場合の計算量です。入れ子ループ法の結合では、各タプルについて相手表のタプルを調べるため、対数ではなく二つのnを掛けた増え方になります。

選択肢ウ（正解）

これは正解だよ。外側のループで一方の表のnタプルを順に取り出し、各回に内側のループで他方の表のnタプルを調べます。したがって比較回数は n×n = n² 回となり、計算量は O(n²) です。

選択肢エ

これは不正解だよ。O(n log n)は、n回の処理に対数回程度の処理が組み合わさる場合の増え方です。ここでは各タプルに対して相手表を全件走査するため、内側の処理はlog nではなくn回であり、全体は n² になります。

学習のポイント

入れ子ループ法では、二つのループの反復回数を掛け合わせて計算量を求めます。