前置き
前回から間が空きましたが、再開します。
基本的には自分のOneNoteにまとめたメモ書きを公開してるだけですが。
第7回は、アルゴリズムです。
ようはプログラミングの基礎的な部分でよく使う知識ですね。
アルゴリズム
流れ図「フローチャート」
順次・選択(if)・繰り返し(while, for)という基本3構造(ダイクストラの基本3構造)を用いてプログラムの骨組みを記述。
ﾌﾟﾛｸﾞﾗﾐﾝｸﾞを1行1行追って確認していくことをトレースという。
探索アルゴリズム
- 線形探索
データを先頭から探索。データがランダムの場合、探索は平均で大体真ん中らへんで見つかることから、
平均探索回数はn/2回、計算量はO(n){基礎理論:情報に関する理論:情報量オーダ}となる。 - 2分探索
データを予め整列させておき、最初に真ん中のデータと探索データを比較。前後どちらに探索したいものがあるかを判断し、
だんだんと探索範囲を1/2にしていく。n回の探索で2^nまでのデータに対応できる。
計算量はO(log n)。 - ハッシュ表探索
ハッシュ関数を利用し探索する。この方法は演算ですぐ格納場所が見つかるため、データ量に関係なく計算量はO(1)となる。
ただし、違うデータ値でハッシュ値が重なるシノニムという問題が起こることがあり、その場合工夫が必要。
シノニムの解決方法として、そのシノニムデータを線形リストによって管理するチェイン法や、次の空き位置にデータを格納するオープンアドレス法などがある。
整列アルゴリズム
昇順や降順にデータを並び替えるアルゴリズム。
- バブルソート
隣りの要素と比較し大小の順が異なる場合入れ替える。隣同士の比較を全て繰り返すので、計算量はO(n^2)。 - 挿入ソート
整列された列に、新たに一つずつ適切な位置に挿入する。挿入位置決定に線形探索を行うので、計算量はO(n^2)。 - 選択ソート
未選択の部分列から、最大(または最小)の値を検索し整列していく。最端の検索を毎回行うので、計算量はO(n^2)。 - クイックソート
最初に中間的な基準値を決め、それよりも大きい値を集めた部分列と小さい値を集めた部分列に要素を振り分ける。
その後、それぞれの部分列の基準値を決めて同様の走査を繰り返す。ランダムなデータの場合、計算量はO(nlog n)。 - シェルソート
ある一定時間おきに取り出した要素から成る部分列をそれぞれ整列させさらに感覚を狭めて繰り返し、
最終的に間隔を1にして完全に整列させる。挿入ソートの発展形。間隔は2^n-1でnを1ずつ減らすので、計算量はO(nlog n)。 - ヒープソート
未整列部分でヒープを構成し、その根から最大値(または最小値)を取り出して整列済の列に移す。
選択ソートの発展形で、計算量はO(nlog n)となる。 - マージソート
未整列のデータを2分する分割動作を完全にバラバラになるまで行い、その後全体をマージ(併合)して整列済のデータ列を作る。
計算量はO(nlog n)だが、マージするためのメモリ量を多く確保する欠点がある。
再帰のアルゴリズム
自分自身をもう一度呼び出すアルゴリズム。
- 文字列処理のアルゴリズム
文字列の探索・置換などがある。
文字列の探索にはBM法などがあり、置換は探索の直後に行われるので、アルゴリズムは探索と同じである。 - 遺伝的アルゴリズム
生物の進化論を利用し、進化を模倣することで最適化問題を解く手法。 - その他のアルゴリズム
色々ある。出題率が低いが、見かけたら覚えたほうがよい。
最後に
ソートの問題は、午前によく出てた記憶があります。
