| 探索法など |
|---|
|
◆ 線形探索法 線形探索法とは、ｎ個あるデータからｍというデータを見つけたい時、データ郡の中を先頭から順番に探索していく方法の事です。 配列のデータが順に格納されていない場合など、この方法でしか ですが、試験では意味を聞かれる事はなく、何回データを比較したか、また平均何回データを探索するかが出てきます。 よく出る過去問題で、ｎ個の昇順に並んだデータがあり、このデータをｍ個のデータ毎のブロックに分割し、 各ブロックの最後尾のデータだけを線形探索することによって、目的のデータのブロックを探し出す。 次に、該当ブロックを線形探索を行い目的のデータを探し出す。この時の平均比較回数はいくつか？ （ｎはｍの倍数であり、該当データは必ず存在する。） 問題では下の図の様に、データを分割すると書いてます。
探索はブロック単位と、ブロックの中で個別という２種類の方法で行われます。 なのでブロック単位とブロックの中で個別、２つの平均を出さないといけません。 まずはブロック単位。ｎはｍの倍数なので、全てのブロックはｍ個あると考えて良いです。 そして平均回数は全探索回数／２で良いので、ブロック単位は 全ブロック数／２ となります。 よって全ブロック数は ｎ／ｍ なので、ｎ／２ｍ がブロック単位の平均回数となります。 次に、ブロックの中で個別の平均探索回数を求めます。 どのブロックであるかは前の探索で見つかっているという前提で良いと思うので、 ここはそのまま ブロックの中のデータ個数／２、よって ｍ／２ で良いと思います。 最後にこの２つを加算したのが総平均探索回数となります。よって ｎ／２ｍ ＋ ｍ／２ となります。 ◆ ２分木探索法
◆ ハッシュ探索法 ハッシュ探索法は、データがハッシュ法（別ページで記述）によって格納された配列が対象になります。 検索したいキー値をハッシュ関数に渡し、取得したハッシュ値をそのまま配列の格納位置としてデータを持ってきます。 ただし、ハッシュ値は衝突をすると言う事を忘れてはいけません。なので格納位置が分かっても、それが正しいデータなのか比較処理が必要です。 もし違っていた場合は、衝突した時の手順に従って順次に検索をしていかないといけません。 ここで言う手順は、実は特に決まっていません。（開発する人が自由に決めていいのです。） ハッシュ法の箇所では＋αの位置に格納していくと記述しました。 その場合で言うと、ハッシュ値＋αの位置を順次検索して比較する処理を繰り返します。 下は「EEEEEE」のデータを検索しようとして、ハッシュ値が 1 だった場合の例です。（αは 3 とします）
|
|||||||||||||||||||||||||||||||||||||||||||||
| TOPページに戻る |