ブロック探索の平均比較回数

整列された $n$ 個のデータを $m$ 個ずつのブロックに分割すると、ブロックの個数は $\frac{n}{m}$ 個となります。探索は次の2段階で行われます。 ブロックの特定:各ブロックの最後尾のデータを線形探索して、目的データが含まれるブロックを探し出します。ブロック数は $\frac{n}{m}$ 個であり、目的のブロックを特定するまでの平均比較回数は、ブロック数が十分に大きいとき約 $\frac{n}{2m}$ 回となります(厳密には $\frac{n/m + 1}{2}$ 回)。 ブロック内の探索:特定されたブロック内(データ数 $m$ 個)を線形探索して、目的のデータを探し出します。$m$ 個のデータから目的データを見つけるまでの平均比較回数は、$m$ が十分に大きいとき約 $\frac{m}{2}$ 回となります(厳密には $\frac{m + 1}{2}$ 回)。 全体の平均比較回数は、これら2つの探索の平均比較回数の和となるため、次のようになります。 $$\frac{m}{2} + \frac{n}{2m}$$ したがってイが正解です。

異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、mは十分に大きく、nはmの倍数とし、目的のデータは必ず表の中に存在するものとする。

出典令和7年度 秋期 高度情報処理技術者試験 午前Ⅰ 問3
ア
m+nmm + \frac{n}{m}
イ
m2+n2m\frac{m}{2} + \frac{n}{2m}
ウ
m+n2m\frac{m + n}{2m}
エ
m2+nm\frac{m}{2} + \frac{n}{m}