【応用情報技術者試験】探索アルゴリズムについて勉強日記俺用メモ！

こんばんはきよです！

今回は探索のアルゴリズムについて勉強したことをメモしていきます！

■参考文献(アフィリエイトリンクです！良かったら購入してください！)

かなり詳しく書かれているのでぜひ！

■線形探索法

・先頭から順番に探す

・整列されていないデータ、使用頻度順に並んでるデータの探索に有効

・平均比較回数 = (N + 1) / 2

・探索対象データの末尾に探索データを追加して終わり判定

– 番兵法

・探索データのキー値からそのデータの格納場所を計算する方法

・２分探索や線形探索より探索時間が短くなる

・格納場所の算出方法をハッシュ関数という

・異なるキー値から同一のハッシュ値が得られてしまうことを衝突(シノニムの発生)という

・シノニムを完全に無くす方法はない

・シノニムの発生時の対応策の一つ

・シノニムが発生した場合は、別のキー値(ハッシュ値+1)を新たなハッシュ値として開いている領域を探す

・椅子取りゲームみたいな感じ(先に座られたら一番近い開いてる椅子を探すみたいな)

・シノニムの発生時の対応策の一つ

・同じハッシュ値を持つデータをポインタで連結リストで繋ぐ方法

最後にまたアフィリエイトリンク貼らせてくださいorz

以上、よろしくお願いいたします。