令和3年度秋期 データベーススペシャリスト 午前Ⅱ 問15

結合計算量を見極める視点

結合操作の計算量を考えるときは、処理の細部を暗記するより、入力規模と処理対象の広がりが増えた際に、作業量がどう変化するかという関係に注目します。前提条件をそろえて比較することが重要です。

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

選択肢を読む際は、単に処理が速いか遅いかではなく、どの入力要因を基準に作業量を見積もっているか、その増え方の説明が一貫しているかだけを確認してください。他の観点を混ぜず、規模との関係に絞ります。

視点

計算量を整理する際は、対象となるデータの規模、処理が参照する範囲、同じ作業が繰り返される条件を切り分けます。具体的な方式名や式ではなく、入力の増加に対する作業量の変化を同じ前提で見比べると、説明の焦点を保ちやすくなります。

確認ポイント

• 入力規模として何を数えているか
• 作業量の増加をどの条件に結び付けているか
• 比較する説明で前提条件がそろっているか

正解

エ

解説

タプル数nの表を二つ結合し、入れ子ループ法で一方の表の各タプルについて他方の表を走査するため、基本的な比較回数はn×nとなる。したがって計算量はO(n²)です。

理由

二つの表はいずれもタプル数がnです。入れ子ループ法では、外側の表の各タプルを処理するたびに、内側の表のタプルを順に調べる。したがって基本的な処理回数は n回×n回、すなわちn²回となり、計算量はO(n²)です。

比較

O(log n)は入力を段階的に絞る処理、O(n)は一回の線形走査、O(n log n)は線形処理と対数的処理の組合せに対応する。今回の前提は二つの表を入れ子ループで調べる構造なので、これらより二重の線形走査に対応する評価が適切です。

選択肢ア

これは不正解だよ。O(log n)は、入力規模が増えても処理回数が対数的にしか増えない場合の計算量である。今回の入れ子ループ法では、二つの表のタプルをそれぞれ線形に調べるため、この対数的な増加では条件と一致しない。

選択肢イ

これは不正解だよ。O(n)は、タプル数nに比例する一回程度の線形走査を表す。今回の処理では、外側の表の各タプルについて内側の表も調べるため、片方だけを走査する場合の線形計算量では表せない。

選択肢ウ

これは不正解だよ。O(n log n)は、線形の処理に対数的な処理が組み合わさる場合の表現である。設問の入れ子ループ法は、片方の表を処理するたびにもう一方を走査する構造なので、n log nとなる条件とは異なる。

選択肢エ（正解）

これは正解だよ。二つの表はいずれもタプル数nであり、入れ子ループ法では外側の各タプルに対して内側の表を走査する。基本的な処理回数はn×n=n²となるため、計算量はO(n²)である。

学習のポイント

入れ子になった反復処理では、各ループの反復回数を掛け合わせて計算量を求める。