アルゴリズム (全82問中2問目)

No.2

異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し,各ブロックの最後尾のデータだけを線形探索することによって,目的のデータの存在するブロックを探し出す。次に,当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで,mは十分大きく,nはmの倍数とし,目的のデータは必ず表の中に存在するものとする。
  • [この問題の出題歴]
  • 応用情報技術者 H21春期 問8
  • 応用情報技術者 H24春期 問9
  • ソフトウェア開発技術者 H17春期 問13
  • ソフトウェア開発技術者 H18秋期 問11

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

線形探索法を2回組み合わせて目的データを探し出すときの平均比較回数を求める問題です。探索するデータ数に注目して考えていきましょう。

線形探索法とは探索データの先頭から順に探索していく方法で、N個のデータの中から目的のデータを探すときの平均比較回数は(N+1)/2回です。(Nが十分に大きいときはN/2回)

最初は、n個のデータをm個のデータごとのブロックに分割した最後尾のみを線形探索します。

 探索するデータ数は、n/m 個

目的のデータがあるブロックを見つけるまでの平均比較回数は、

 (n/m)÷2=n/2m 回

です。

2回目は、1回目の探索によって見つけた目的のデータがあるブロック内を線形探索します。

 探索するデータ数は、m個

目的のデータを見つけるまでの平均比較回数は、

 m/2 回

です。

つまり、1回目と2回目の平均比較回数を合わせた06i.gif/image-size:56×24が正解となります。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop