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

問題文

相異なる

n

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

m

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

m

は十分大きく、

n

は

m

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

選択肢

ア：m+t-1

イ：n/m + n/(2m)（正解）

ウ：n/m + n^2/(2m^2)

エ：n/(2m)

相異なるデータのブロック分割による探索の平均比較回数【午前2 解説】

要点まとめ

結論：平均比較回数は「 $n / m + n / (2 m)$ 」で表され、選択肢イが正解です。
根拠：まずブロックの最後尾を線形探索し、次に該当ブロック内を線形探索するため、比較回数は両者の和となります。
差がつくポイント：ブロック数とブロック内探索の平均回数の計算を正確に理解し、式の意味を正しく把握することが重要です。

正解の理由

選択肢イの「

n / m + n / (2 m)

」は、

ブロック数は $n / m$ 個であり、目的のデータが必ず存在するため、ブロックの最後尾を線形探索する平均比較回数は $n / m$ 。
目的のデータがブロック内に均等に分布すると仮定すると、ブロック内の線形探索の平均比較回数はブロックサイズ $m$ の半分、すなわち $m /2$ 。
これを $m = n / m$ の形に直すと、 $m /2 = n / (2 m)$ となる。
したがって、合計は $n / m + n / (2 m)$ となり、選択肢イが正解です。

よくある誤解

ブロックの最後尾探索とブロック内探索の比較回数を混同し、単純に

m + t - 1

のような誤った式を選ぶことがあります。
また、二乗の項が入った複雑な式を選ぶ誤りも多いです。

解法ステップ

データ数 $n$ とブロックサイズ $m$ の関係を確認し、ブロック数を $n / m$ とする。
ブロックの最後尾を線形探索する平均比較回数は $n / m$ 。
ブロック内の線形探索は平均でブロックサイズの半分、すなわち $m /2$ 。
$m /2$ を $n$ と $m$ の関係式で表すと $n / (2 m)$ 。
両者を合計し、平均比較回数は $n / m + n / (2 m)$ となる。
選択肢の中からこの式に合致するものを選ぶ。

選択肢別の誤答解説

ア: $m + t - 1$ は問題文にない変数 $t$ が不明であり、意味が不明確です。
イ: $n / m + n / (2 m)$ は正しい平均比較回数の式です。
ウ: $n / m + n^{2} / (2 m^{2})$ は二乗の項が入っており、探索回数の平均として過剰に大きい値を示します。
エ: $n / (2 m)$ はブロック内探索の平均のみで、ブロックの最後尾探索を考慮していません。

補足コラム

この問題は「ブロック探索法（ブロック線形探索）」の典型例です。
ブロック探索は、データが整列されている場合に、全体を小さなブロックに分割し、ブロックの代表値（ここでは最後尾のデータ）を先に探索することで、探索効率を改善します。
この手法は二分探索ほど高速ではありませんが、データ構造が単純な場合に有効です。

FAQ

Q: なぜブロック内の平均探索回数は

m /2

なのですか？
A: 線形探索では目的のデータがブロック内のどこにあるか均等に分布すると仮定し、平均的に半分の位置で見つかるためです。

Q: ブロックの最後尾探索はなぜ線形探索なのですか？
A: 問題文で「各ブロックの最後尾のデータだけを線形探索する」と明示されているためです。

関連キーワード: ブロック探索法、線形探索、平均比較回数、データ構造、探索アルゴリズム

← 前の問題へ次の問題へ →

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

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

問題文

選択肢