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

関係結合の計算量を考える視点

結合操作の計算量を検討するときは、処理対象の規模だけでなく、利用できる構造や処理の進み方が見積もりにどう影響するかを整理し、同じ前提で増え方を丁寧に比べましょう。

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

一つの観点として、入力データの規模が増えたときに、比較や探索の対象がどのように広がるかを追い、前提となる処理単位と対象範囲の関係を具体的かつ丁寧に確認してください。

視点

計算量を比べる際は、まず入力の大きさを定め、その大きさに応じて処理対象が増える仕組みを追います。次に、利用する順序付けや索引などの前提が示されているかを確認し、同じ条件で増え方を比較します。特定の方式を決めつけず、条件の違いを分けて考えることが大切です。

確認ポイント

• 入力データの大きさとして、どの集合や件数を基準にしているか
• 処理対象の組合せや探索範囲が、入力の増加に伴ってどう変わるか
• 利用できるデータ構造や前処理など、計算量の前提条件が何か

正解

ウ

解説

入れ子ループ法で二つの表を結合する場合、外側の表の各タプルについて内側の表を調べます。そのため、両方の表のタプル数に応じて処理回数が増加します。

理由

外側の表の各タプルに対して、内側の表の全タプルを順に調べるため、比較回数はおおむねn×n回になります。したがって計算量はO(n²)です。

比較

O(n)は一方の表を一度調べる程度、O(log n)は入力を段階的に絞る処理、O(n log n)はソートなどを伴う場合に典型的です。単純な入れ子ループの結合には適しません。

選択肢ア

これは不正解だよ。O(n)は、入力サイズnに比例して処理が増える計算量です。しかし入れ子ループ法では、外側の各タプルについて内側の表も調べるため、片方の表だけを一度確認する場合より多くの処理が必要になります。

選択肢イ

これは不正解だよ。O(log n)は、入力を一定の割合で絞り込むような処理で現れる計算量です。入れ子ループ法による結合は、表のタプルを順番に確認する処理であり、対数的に探索範囲を縮める方法ではありません。

選択肢ウ（正解）

これは正解だよ。入れ子ループ法では、外側の表の各タプルに対して内側の表の各タプルを調べます。両方の表のタプル数がnなので、処理回数はおおむねn×nとなり、計算量はO(n²)です。

選択肢エ

これは不正解だよ。O(n log n)は、線形回数の処理に加えて、ソートや分割統治など対数的な処理が組み合わさる場合に典型的です。単純な入れ子ループ法では、そのような構造ではなく二重の反復が発生します。

学習のポイント

入れ子ループ法の反復回数と計算量の関係を理解する。