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

選択肢

• アm + n/m
• イm/2 + n/2m
• ウn/m
• エn/2m

正解と解説

正解：イ m/2 + n/2m

ブロック数はn/m個なので、最後尾データを線形探索して目的のブロックを見つけるまでの平均比較回数は(n/m)/2＝n/2mとなる。次にそのブロック内のm個を線形探索する平均比較回数はm/2である。両者の和はm/2＋n/2mとなる。

選択肢ごとの解説

• ア線形探索の平均比較回数は要素数の約半分になるため、1/2の係数が抜けている。
• イ正解。ブロック探索の平均n/2mとブロック内探索の平均m/2の和である。
• ウブロック数そのもので、ブロック内の探索回数が含まれておらず、平均も考慮していない。
• エブロックを特定するまでの平均比較回数だけで、ブロック内の線形探索が抜けている。

同じ分野の他の問題

• A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、デ…2021年度 春期 問2
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 問3
• 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めた…2024年度 春期 問3
• あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3
• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2023年度 春期 問6