応用情報技術者 2009年春期午前2 問08

問題文

相異なる

n

個のデータが昇順に整列された表がある。この表を

m

個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、

m

は十分大きく、

n

は

m

の倍数とし、目的のデータは必ず表の中に存在するものとする。

🖊️ 解答を隠して解いてみる

選択肢

ア：

m + t - 1

イ：

\frac{n}{m} + \frac{n}{2 m}

（正解）

ウ：

\frac{n}{m} + \frac{n ^{2}}{2 m ^{2}}

エ：

\frac{n}{2 m}

🔒 解説は解答すると表示されます

ブロック探索の比較回数【午前2解説】

正解の理由

昇順整列表を「ブロック毎に末尾だけを見てブロックを決め、当該ブロック内を線形探索する」手順に沿って、1回の探索で行う比較数の期待値を厳密に求めると、

E = \frac{n / m + m}{2}

となります。ここで

B = n / m

をブロック数、ブロック内の要素数を

m

としています（問題文の記法に合わせているため注意）。式の意味は「ブロック末尾を調べる比較の期待値」が

(B + 1) /2

、「選ばれたブロック内を線形探索する比較の期待値」が

(m - 1) /2

であり、それらを加えて平均化すると上式になるためです。

（注）設問の選択肢表記ではイが答案キーになっていますが、上の厳密導出では上式が正しく、選択肢のどれにも完全一致しない点については下で詳しく説明します。

解法ステップ

変数整理
- 全データ数 $n$ 、ブロックの要素数 $m$ 、ブロック数 $B = n / m$ （ $n$ は $m$ の倍数）。
- 目的データの位置を一様ランダムとする（問題の条件）。
ブロック末尾比較の期待値
- 目的が第 $k$ ブロックにある確率は各ブロックで $m / n$ で等しい。第 $k$ ブロックを見つけるためにブロック末尾を順に $1, 2, \dots, k$ 回比較する。
- よってブロック末尾比較数の期待値は $E_{block} = \frac{1}{B} \sum_{k = 1}^{B} k = \frac{B + 1}{2} .$
ブロック内線形探索の期待値（「末尾一致なら内部探索を省く」場合）
- ブロック内での目的の位置を $r \in {1, \dots, m}$ とする。 $r = m$ （末尾）の場合は既にブロック末尾比較で見つかるため内部探索は不要（比較回数 0）。それ以外は位置 $r$ まで線形に比較するため比較回数は $r$ 。
- したがってブロック内比較の期待値は $E_{inner} = \frac{1}{m} \sum_{r = 1}^{m - 1} r = \frac{m - 1}{2} .$
総期待値
- 合計して $E = E_{block} + E_{inner} = \frac{B + 1}{2} + \frac{m - 1}{2} = \frac{B + m}{2} = \frac{n / m + m}{2} .$

5.（参考）別のカウント規約を採る場合

もし「ブロック末尾で目的と一致しても、当該ブロック内を改めて先頭から走査して目的を見つける（末尾要素を二重に比較する）」という非効率な手順を仮定すると、ブロック内期待値が $(m + 1) /2$ 、ブロック末尾が $(B + 1) /2$ のままなので $E^{'} = \frac{B + m + 2}{2}$ となります。ここで末尾一致で内部探索を省くか否かで差が出ることに注意してください（以降の議論はこの「どの比較を二重に数えるか」の区別が鍵です）。

選択肢別の誤答解説

ア: $m + t - 1$
- 選択肢自体に未定義変数 $t$ が含まれており問題記述と整合しない。設問のパラメータは $n, m$ のみであるため成立しない。
イ: $\frac{n}{m} + \frac{n}{2 m}$
- これを整理すると $\frac{3}{2} \cdot \frac{n}{m}$ となります。前節で正しく導出した式は $\frac{n / m + m}{2}$ であり、一般には一致しません。イが当てはまるのは、 $m$ と $n / m$ が等しい特殊ケース（すなわち $m^{2} = n$ ）に限られます。したがって一般解としては誤りです。ただし、もし受験問題で「ブロック数を $m$ とし、ブロック長が $n / m$ と表記される」など変数の意味が入れ替わって説明されていたり、別のカウント規約（末尾比較を常に内部探索でも再比較する等）が暗黙に使われている場合、解釈のズレでこの式が「答案キー」として出ることがあります（設問の解釈注意）。
ウ: $\frac{n}{m} + \frac{n ^{2}}{2 m ^{2}}$
- 右辺は $\frac{n}{m} (1 + \frac{n}{2 m})$ の形で、 $n$ に対して二次的に増える項を含む。導出された期待比較回数は $n$ に比例（一次）ではなく、 $m$ と $n / m$ の和の半分なのでこの二次項は不適切です。
エ: $\frac{n}{2 m}$
- これは小さすぎます。ブロック末尾の比較やブロック内の探索を考慮すると、少なくともブロック末尾の比較（平均で $(n / m + 1) /2$ 回）が必要であり、これだけで $\frac{n}{2 m}$ を超えるため合いません。

よくある誤解

「末尾で一致した場合も必ずブロック内を探索する」と暗黙に仮定してしまう誤り
- 末尾一致のときは内部探索を行わないのが自然で、二重に比較するかどうかで期待値が変わります。問題文では「ブロック末尾のデータだけを線形探索してブロックを探し出す」とあるため、末尾で一致したらその時点で探索は終了すると読むのが妥当です。
ブロック末尾比較の期待値を $n / m$ （全ブロック数そのまま）と誤って扱う誤り
- 「目的がどのブロックにあるか」は均等確率なので、ブロック末尾の比較回数は平均して $(1 + 2 + \dots + B) / B = (B + 1) /2$ となります。単に $B$ とするのは誤りです。

補足コラム

最適な $m$ （ブロックサイズ）について
- 探索コストの近似式 $E \approx \frac{B + m}{2} = \frac{n / m + m}{2}$ を $m$ で最小化すると、連続変数として微分して最小化すると $m = n$ （ただし整数に丸める必要あり）。すなわちブロックサイズをデータ数の平方根程度に取ると期待比較回数が最小になります（平方根分割法に相当）。
実装上の注意
- 実際のコードでは「末尾で一致したらすぐ返す」か「内部探索を常に行うか」をはっきりさせ、比較回数を厳密に数えるとよいです。二重比較を避ける小さな工夫（末尾で一致したら内部ループをスキップ）は効率的です。

FAQ Q1: 末尾一致のとき内部探索を「1回だけ短縮」してよいのか？
A1: はい。ブロック末尾比較で目的と一致がわかったら探索は終了です。内部探索を続ける理由はありません（ただし設計上冗長に検索を行う実装がある場合は別）。

Q2: 期待値の計算で端点（+1 や -1）の扱いはどうするか？
A2: 厳密に扱うと

(B + 1) /2

や

(m - 1) /2

のように端点が現れます。試験問題で「m は十分大きい」といった条件が付く場合はこれらの ±1 は無視して近似的に扱うことがありますが、厳密解を導けるなら端点も正確に扱うべきです。

Q3: 与えられた選択肢が導出式と一致しない場合は？
A3: 変数の定義誤解や比較回数のカウント規約（末尾を二重に数えるか否か）による可能性があります。設問文の記述を注意深く読み、どの要素を比較として数えているかを明確にしてください。今回の厳密導出は

E = (n / m + m) /2

です。

関連キーワード: ブロック探索、線形探索、期待比較回数、探索アルゴリズム、平方根分割法

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！