異なる ｎ 個のデータが昇順に整列された表がある。
この表を ｍ 個のデータごとのブロックに分割し、
各ブロックの最後尾のデータだけを線形探索すること
によって、目的のデータの存在するブロックを探し出す。
次に、当該ブロック内を線形探索して目的のデータを
探し出す。このときの平均比較回数を表す式はどれか。
ここで、ｍ は十分に大きく、ｎ は ｍ の倍数とし、
目的のデータは必ず表の中に存在するものとする。
ア ｍ ＋ ｎ／ｍ
イ ｍ／２ ＋ ｎ／２ｍ
ウ ｎ／ｍ
エ ｎ／２ｍ
Ｎ個のデータを線形検索した場合、平均比較回数は Ｎ／２である。
これを踏まえる。
ブロックの個数は ｎ／ｍ個であるから、
目的のデータが存在するブロックを探し出すための平均比較回数は ｎ／２ｍ 回である。
さらに、当該ブロック内で目的のデータを探し出すための平均比較回数は ｍ／２ 回である。
従って、平均比較回数は ｍ／２ ＋ ｎ／２ｍ である。
EXCEL ＶＢＡのご相談なら ファーストマクロ へ
タグ：平均比較回数
