応用情報技術者試験の学習メモ アルゴリズム＜探索編＞

徹底攻略 応用情報技術者教科書 平成27年度 (Tettei Kouryaku JOHO SHORI)

 基本ゆえについ後回しになるアルゴリズム。

覚えてもすぐに記憶の彼方に去って行ってしまうアルゴリズム。

・・・はい、頑張って覚えます。

１．線形探索

２．２分探索

３．ハッシュ法探索

の順にまとめました。

１．線形探索

データを先頭から順番に探索してく単純なアルゴリズム。

・時間がかかる

n個のデータで探索を行うと、

平均比較回数	〔(N+1)/2〕
最大比較回数	N
計算量	O(n)

 となる。

２．２分探索（バイナリサーチ）

データをあらかじめ整列しておき、 最初に真ん中のデータと探索するデータを比較する。探索するデータとの大小関係で探索する配列を分割しながらデータを探し出すアルゴリズム。

・効率よく見つかる

・あらかじめ整列されたデータに対して高速

平均比較回数	log2N
最大比較回数	〔log2N〕+1
計算量	O(log n)

３．ハッシュ法探索

ハッシュ表（ハッシュテーブル）といわれるデータ配列を用意し、その格納場所のキーであるハッシュ値をハッシュ関数で算出する方法。

例えば、ハッシュ関数 H(x) = x%5 を設定してデータ「17」を探索する。

H(17) = 17%5 = 2 となり、ハッシュ値が「２」の場所をみるとデータ「17」が見つかる。

ハッシュ値	データ
0	40
1	21
2	17
3	3
4	14

演算ですぐに格納場所が見つかるのでデータ量に関わらず計算量はO(1)となる。

・高速

・シノニムの問題がある

・シノニムの解決にチェイン法やオープンアドレス法がある

平均比較回数	1
最大比較回数	N
計算量	O(1)

  次は整列アルゴリズムを覚えます。

記事を追加しました！

yk-studyworks.hatenablog.com

 以上、参考にどうぞ。

================================================

応援クリックお願いします☆　<m(__)m>

にほんブログ村

にほんブログ村

スポンサーリンク