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

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

関係データベースの結合を考えるときは、処理全体を一括して見るのではなく、入力の大きさと支配的になりやすい処理の関係に注目し、前提条件をそろえて比較することが大切です。

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

この問題では、結合方法の細かな暗記よりも、二つの入力規模が計算量の見積もりにどう影響するか、また比較の前提が何かを一つの軸で整理して一つずつ丁寧に確認しましょう。

視点

計算量を検討する際は、対象となる入力の規模、処理の繰り返し方、利用できる前処理や記憶領域などを分けて捉えます。そのうえで、どの要因が増加を左右するかを見極め、同じ条件で整理します。

確認ポイント

• 入力の規模をどの変数として捉えるか確認する
• 処理の中で繰り返しが発生する箇所に注目する
• 比較する際の前提条件がそろっているか確認する

正解

ウ

解説

入れ子ループ法では、一方の表の各タプルについて、もう一方の表のタプルを順に調べます。両表のタプル数がともにnなので、比較回数はn×n=n²回となり、計算量はO(n²)です。

理由

外側のループは一方の表のn個のタプルを処理し、外側の各反復で内側のループがもう一方の表のn個のタプルを調べます。したがって比較回数は、単位を比較回数としてn回×n回=n²回です。定数や低次の項を除けば、計算量はO(n²)になります。

比較

O(2n)は入力サイズに比例する線形時間、O(log n)は対数時間、O(n log n)はそれらの中間的な増加です。今回のように、各要素に対して別の表全体を走査する処理では、単一ループや分割処理とは異なる二重の増加になります。

選択肢ア

これは不正解だよ。O(2n)は、定数2を含む線形時間を表します。二つの表のタプル数がともにnで、外側の各タプルに対して内側でもn個を調べるため、処理回数は2nではなくn×n回になります。定数を無視してもO(n)であり、設問の入れ子走査の増え方とは一致しません。

選択肢イ

これは不正解だよ。O(log n)は、入力が増えても処理回数の増加が非常に緩やかな対数時間を表します。しかし入れ子ループ法の結合では、一方の表の各タプルに対して他方の表を調べるため、二つのn回の反復が組み合わさります。対数的な探索構造を前提とする計算量ではありません。

選択肢ウ（正解）

これは正解だよ。外側のループで一方の表のn個のタプルを順に処理し、各反復で内側のループがもう一方の表のn個を走査します。比較回数はn回×n回=n²回となります。したがって、定数や低次の項を除いた計算量はO(n²)です。

選択肢エ

これは不正解だよ。O(n log n)は、線形回数の処理に対数回程度の処理が組み合わさる場合などに現れる計算量です。設問の入れ子ループ法では、内側の処理は対数回ではなく、もう一方の表のn個を走査します。そのため処理回数はn×log nではなくn×n回です。

学習のポイント

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