表探索の平均比較回数を解説

異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。

次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，mは十分大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。

• ブロック全体から目当てのブロックを探すのに約 n/(2m) 回
• 選んだブロック内から実際のデータを探すのに約 m/2 回
• 合計は (m/2) + (n/(2m))

こうして、「mが十分大きい」「nはmの倍数」「データは必ずある」という条件のもとで、平均的な比較の回数を簡単に表すと、

になるわけです。