応用情報技術者試験 平成30年春 午前問6 解説付き過去問
問題
異なるn個のデータが昇順に整列された表がある。
この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。
次に、当該ブロック内を線形探索して目的のデータを探し出す。
このときの平均比較回数を表す式はどれか。
ここで、mは十分大きく、nはmの倍数とし、目的のデータは必ず表の中に存在するものとする。
正解
解説
この問題は、昇順に整列された n 個のデータに対し、m 個ずつのブロックに分割したうえで、目的のデータを効率的に探索する際の平均比較回数を求めるものです。探索方法としては、次の2段階の線形探索が行われます。
- 第1段階：ブロックの末尾要素に対する線形探索
n 個のデータを m 個ずつに分割することで、ブロック数は nm 個となります。
各ブロックの末尾データは昇順に並んでおり、この末尾要素を線形に探索して、目的のデータが存在するブロックを特定します。
目的のデータは必ず存在するという条件から、線形探索における平均比較回数は、最小1回・最大 nm 回のため、平均は n2m 回となります。 - 第2段階：該当ブロック内での線形探索
該当ブロックには m 個のデータがあり、これらを順番に比較して目的のデータを特定します。
平均比較回数は m 個のデータに対して m2 回です。
以上より、2段階の線形探索における平均比較回数の合計は、次の式で表されます。
m2 ＋ n2m