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

問題文

相異なる

n

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

m

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

m

は十分大きく、

n

は

m

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

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

選択肢

ア：

m + \frac{n}{m}

イ：

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

（正解）

ウ：

\frac{n}{m}

エ：

\frac{n}{2 m}

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

ブロック分割した表の探索【午前2解説】

正解の理由

表は

m

個ずつのブロックに分かれているので、ブロックの数は

\frac{n}{m}

です。まず各ブロックの最後尾のデータを先頭のブロックから順に比較して、目的のデータがあるブロックを見つけます。目的のデータはどのブロックにも同じ確率で存在するので、この比較の平均回数はブロック数の半分の

\frac{n}{2 m}

回です。次にブロック内の

m

個のデータを線形探索するので、その平均比較回数は

\frac{m}{2}

回です。合計すると

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

となり、イが正解です。

解法ステップ

ブロックの数を求める： $\frac{n}{m}$ 個
ブロックを探す比較の平均回数：ブロック数の半分で $\frac{n}{2 m}$ 回（ $m$ は十分大きいので、「＋1」などの細かい差は無視する）
ブロック内の線形探索の平均回数： $\frac{m}{2}$ 回
合計： $\frac{m}{2} + \frac{n}{2 m}$

選択肢別の誤答解説

ア： $m + \frac{n}{m}$ は、ブロックの探索とブロック内の探索がどちらも最後まで（最悪の場合）比較したときの回数です。平均ではありません。
イ： $\frac{m}{2} + \frac{n}{2 m}$ は、二つの段階の平均比較回数の合計です。
ウ： $\frac{n}{m}$ は、ブロックの数（ブロックを探す最大の比較回数）だけで、ブロック内の探索が含まれていません。
エ： $\frac{n}{2 m}$ は、ブロックを探す平均回数だけで、ブロック内の探索が含まれていません。

よくある誤解

平均回数ではなく最大回数で計算すること。線形探索の平均比較回数は、データ数の約半分です。
二つの段階の一方だけを数えること。ブロックを探す比較と、ブロック内を探す比較の両方を足します。

補足コラム

平均比較回数

f (m) = \frac{m}{2} + \frac{n}{2 m}

は、

m = n

のときに最小の

n

になります。ブロックの大きさを

n

にすると、全体を線形探索する場合（平均

\frac{n}{2}

回）より大幅に比較回数を減らせます。

FAQ

Q. なぜ「＋1」を考えなくてよいのですか？
A.

k

個のデータを線形探索するときの平均比較回数は正確には

\frac{k + 1}{2}

回ですが、問題文に「

m

は十分大きく」とあるので、近似として

\frac{k}{2}

回とみなしています。

関連キーワード: 線形探索、平均比較回数、ブロック探索、計算量

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！