高度情報処理技術者試験・情報処理安全確保支援士試験 令和7年度 秋期 午前I 問3

【正解】イ

画像の各式は、アがm＋n／m、イがm／2＋n／（2m）、ウがn／m、エがn／（2m）です。まず、n個のデータをm個ずつに分けるので、ブロック数はn／m個です。目的のデータが各位置に同じ確率で存在すると考えると、ブロック末尾を線形探索して目的のブロックに到達するまでの比較回数は、平均でブロック数の約半分、すなわちn／（2m）回です。次に、見つけたブロック内にはm個のデータがあり、線形探索の平均比較回数は約m／2回です。したがって、全体の平均比較回数は、n／（2m）＋m／2となるので、イが正解です。厳密には端点による定数項が加わりますが、mが十分に大きいという条件から省略します。

アのm＋n／mは誤りです。これは、ブロック探索とブロック内探索の両方で末尾まで比較する場合の最大比較回数に相当し、平均比較回数ではありません。 ウのn／mは誤りです。これはブロックの総数を表す式であり、ブロック内を探索する比較回数が含まれていません。 エのn／（2m）は誤りです。これは目的のブロックを探す第1段階の平均比較回数だけであり、第2段階が欠けています。

【ポイント】 二段階探索では、「ブロックを探す比較回数」と「ブロック内を探す比較回数」を加算します。 平均比較回数m／2＋n／（2m）は、m＝√n付近で最小となり、その値は約√n回です。 線形探索の平均は要素数の約半分、最大は要素数と覚えておくと便利です。