問題プレビューID: ba6fb2ff応用情報技術者試験 2012年(平成24年度)春期 午前

問 9
応用情報技術者試験 2012年(平成24年度)春期 午前

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

解説

正解は「イ」です。

比較は「ブロックの探索」と「ブロック内の探索」の 2 段階に分けて考えます。

  1. ブロックの探索:n 個のデータを m 個ずつに分けると,ブロック数は n/mn/m 個です。各ブロックの最後尾のデータを先頭から線形探索するとき,目的のブロックが見つかるまでの平均比較回数は約 (n/m)/2=n/(2m)(n/m)/2 = n/(2m) 回です。
  2. ブロック内の探索:見つけたブロック内(m 個)を線形探索するときの平均比較回数は約 m/2m/2 回です。

これらを合計すると,平均比較回数は m2+n2m\dfrac{m}{2} + \dfrac{n}{2m} となります。

  • ア: m+nmm + \dfrac{n}{m} は比較回数の見積りとして過大です。
  • ウ: nm\dfrac{n}{m} はブロックの探索のみを考えた場合の最大比較回数に相当し,平均ではありません。
  • エ: n2m\dfrac{n}{2m} は第 1 段階(ブロックの探索)のみの平均比較回数です。

関連問題

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