基本情報シリーズ☆第二回～アルゴリズム・計算量～

今日はアルゴリズムの問題に引っかかった。
基本的なアルゴリズムは覚えとく必要あり。ということで，一通り復習。

◎探索
　①線形探索：N個の要素を先頭から１個ずつチェック。
　　　　　　　　 最大N回チェック。O（N）
　②２分探索：N個の要素（ソート済み）の中央の値を比較。
　　　　　　　　 その後，要素の左半分or右半分の中央の
値を比較。以降繰り返し。
　　　　　　　　 最大比較回数はlog_2_N+1回。O(log_2_N)

◎ソート
　①バブルソート：隣り合う要素で大小比較し，必要に応じて
入れ替え。最大比較回数はN（N-1）/2回。
　　　　　　　　　　　O(N^2)
　②選択ソート：要素の中から最大値を選択し，要素の最後と
　　　　　　　　 入れ替え。以降，最大値と最後から2番目，
　　　　　　　　　 ・・・と繰り返す。
　　　　　　　　　 最大比較回数はN（N-1）/2回。O(N^2)
　③挿入ソート：ソート済み要素の後ろから順次比較，追加の
　　　　　　　　　 位置を探して挿入。
　　　　　　　　　 最大比較回数はN（N-1）/2回。O(N^2)
　④クイックソート：要素の中から1個選抜し，選抜要素を軸に
　　　　　　　　　 大小のグループに分ける。それぞれの
　　　　　　　　　　グループで同様にグループ分割を実行
　　　　　　　　　　（各グループの要素が1個になるまで
　　　　　　　　　　繰り返し）。
　　　　　　　　　　　すべての要素が1個になることで，ソート完了。
　　　　　　　　　　　最大比較回数はN（N-1）/2回。O(N^2)
　　　　　　　　　　　平均計算量はO(N log_N)
※以降は概念のみ
　⑤マージソート：要素を1個になるまで分割し，要素を順次マージ。
　⑥シェルソート：挿入ソート改良版。比較する要素の一定間隔
　　　　　　　　　　 空けて整列。以降，間隔を1ずつ小さくして
　　　　　　　　　　 整列し，最終的に間隔が1になり，挿入
　　　　　　　　　　 ソートの実行でソート完了。
　⑦ヒープソート：ヒープの根の要素を取り出す（最大値）。残りの
　　　　　　　　　　要素でヒープ再構築し，以降ループ。