問題プレビューID: 1f46d371情報処理安全確保支援士試験 2025年(令和7年度)秋期 午前I

問 3
情報処理安全確保支援士試験 2025年(令和7年度)秋期 午前I

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

解説

ブロックの数は n/mn / m 個である。各ブロックの最後尾だけを先頭から線形探索するので,目的のブロックを見つけるまでの平均比較回数は (n/m+1)/2≒n/(2m)(n / m + 1) / 2 \fallingdotseq n / (2m)(m が十分に大きいので近似)である。次にブロック内 m 個を先頭から線形探索する平均比較回数は (m+1)/2≒m/2(m + 1) / 2 \fallingdotseq m / 2 である。合計すると m/2+n/(2m)m / 2 + n / (2m) となり,「イ」が正解である。

関連問題

本文が同じ・似ている問題を表示しています