線形探索について気になったとこあるから書いておく
–平成25年度【春期】【秋期】基本情報技術者合格教本 P73 ここから–
線形探索法では、探索データをあらかじめ最後に配置しておくことがあります。
これを番兵といいます。番兵を用いると、必ず探索データを最後に見つけること
ができるのでデータ件数を気にすることなく終了の半定が容易にできます。
データ件数がN件のとき、
平均探索回数=(N+1)÷2回 最大探索回数=N回
–平成25年度【春期】【秋期】基本情報技術者合格教本 P73 ここまで–
上記のように書いてあった。
番兵ありなら、最大探索回数=N+1回だろ。
というわけで、番兵ありと番兵なしで次のようになるはず。
番兵ありの場合
平均探索回数=(N+1)÷2回 最大探索回数=N+1回
番兵なしの場合
平均探索回数=N÷2回 最大探索回数=N回
今度、基本情報技術者試験で出て来る「線形探索」に関する問題を探してみる。