ITパスポート対策　メモ11　アルゴリズム

ITパスポート対策メモ11についてです。今回はみんな大嫌いな、アルゴリズムです。ここで、高得点を取れたら、基本情報技術者試験の午後で合格できますよね。アルゴリズムを制したものが、基本情報技術者試験を制するともいわれますよね。

ここまでくると過去記事が邪魔になってきますね。そんなことないですね。積み重ねた歴史を、振り返っていますね。

さて、本題に入りますかね。

アルゴリズム・・・プログラムの考え方のことです。簡単に言うと、思考プロセスです。

繰り返し構造

VBAで例えると、

条件が満たされている間　Do...While...

条件が満たされているまで Do...Until...

代表的なアルゴリズム

探索のアルゴリズム

探索とは検索とも呼ばれます。

線形探索法＝リニアサーチ＝順次探索法・・・データを先頭から末尾まで順番に探していくアルゴリズムのことです。探索回数はn/2回です。

番兵法・・・目的のデータを配列の最後に追加しておく処理のことを言います。

2分探索法・・・配列に格納されている中央のデータと目的のデータを比較し、一致しなければ、中央のデータの前半か後半のいずれかに探し出す範囲のことです。

（整列されているという条件付き）例辞書のイメージです。調べることがめんどくさいときに、ぱっと開いて、それより前か後かで判断するようなものです。

最短で一回です。最高でlog2n+1回です。平均でlog2n回です。

半分ずつ範囲を狭めて、検索するものです。

ハッシュ表探索法・・・データを格納するときにあらかじめ関数を使って、データの格納位置を決め、データを探し出すときには、同じ関数を使って格納するアルゴリズムのことです。

データの格納位置をハッシュキー、ハッシュ値、ハッシュキーを決めたり、探し出す関数をハッシュ関数、データを格納した表をハッシュ表といいます。

シノニム・・・ハッシュ表における値の衝突のことです。

マージ（併合）・・・ここでは、2つの配列のデータの並び順はそのままで、一つにまとめることです。