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

選択肢

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

正解と解説

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

表はn÷m個のブロックに分かれる。まず各ブロック末尾のデータを線形探索するので、目的のブロックが見つかるまでの平均比較回数はブロック数の半分、すなわちn/2m回である。次に見つけたブロック内でm個のデータを線形探索するので平均m/2回かかる。両者を足したm/2＋n/2mが答えとなる。

選択肢ごとの解説

• ア最悪の場合の比較回数に相当し、平均を問う設問には合わない。
• イ正解。ブロック探索の平均n/2mと、ブロック内探索の平均m/2の和である。
• ウブロック数そのもので、ブロック内探索の分が抜けている。
• エブロック探索の平均だけで、ブロック内の線形探索を数えていない。

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 午前 問6
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 午前 問6
• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2023年度 春期 午前 問19
• 従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における…2023年度 春期 午前 問6
• 自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力…2018年度 秋期 午前 問27