アルゴリズムと計算量

アルゴリズムとは、問題や課題を解決するための処理手順をもれなく表現した考え方のこと。
プログラムにおけるアルゴリズムの代表的なものとして、ソート（並び替え）と__探索__がある。

アルゴリズムと計算量

アルゴリズムには結果が出るまでにかかる時間の特徴を表す計算量という考え方がある。
計算量は__O記法__という表し方をする。

• O(1)
  • データ数nにかかわらず一定、nが増えても計算量は等しい。
• O(n)
  • 比例なので、データ量が２倍増えると、計算量も２倍増える。
• O(log n)
  • 計算量を求める場合は底を２として考える。nが２倍、３倍と増えても、計算量は１、２と増える程度なので、データ量が多い場合に有用。
• O（n log n）
  • 先述のO(n log)にnの計算量がかけられたもの。
  • nが２倍になると、計算量は約２．５倍、１０倍になると２０倍、１００倍になると３００倍になる。
• O(n^2)
  • ｎ個の要素を用いた総当りの組み合わせを求める場合がこのパターンに当てはまる。大きなデータを扱うと莫大な処理時間になるので、実用的ではない。

ソートアルゴリズム

バブルソート

隣り合う要素の大小を比較して整列させる。
昇順に並び替えるときは、基準となる要素と隣の要素を比較して、基準の要素のほうが大きれば入れ替え、そうでない場合は入れ替えず、基準となる要素をひとつとなりにずらす。
これを繰り返し最終的に正しい順序に並び替える。
総当りで比較していくので、O(n^2)。

挿入ソート

まず１番目と２番目の要素を比較し、要素の順番が逆なら入れ替え、正しければそのままにする。
次に３番目の要素を正しく並んでいる１番目、２番目の要素と比較し、正しい位置に挿入する。
以降の要素もひとつずつ既に並び替えた整列と比較し、正しい順に並ぶように挿入することを繰り返す。
総当りさせるので__O(n^2)__。

マージソート

並び順がばらばらになっている要素を繰り返し２つに切り分け、要素数が１になるまで分解する。
分解した配列ごとに大小を比較し、並び替えたものを合併していく。小さく切り分けたソート済の要素を次々に合併して、すべての要素を正しい順番に並び替える。
並び替えの際に合併するので、マージソートという。
計算量は、はじめに分割する際に２つに切り分けていくので__O(log n)__、並び替えの際に要素の数だけ比較をするので__O(n)__かかる。よって、__O(n log n)__となる。

探索アルゴリズム

探索とは、特定の条件に当てはまるデータを探し出すこと。求める要素と一致する要素が見つかるまで探索をします。

リニアサーチ（線形探索）

一直線に並べたリストを先頭から順に目的の要素かどうか確認していく。一致する要素がでれば探索終了。
最もシンプルな探索アルゴリズム。
計算量は__O(n)__。

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

予め対象のデータを昇順に並べておく必要あり、
探したいデータと、探したい配列の中央の要素を比較し、それより大きいのか、小さいのかによって、次回探す範囲を絞り込みます。例えば、目的の要素が中央の要素より大きれば、大きい方の半分のリストを対象に再度中央の要素を確認し、目的の要素と比較します。
このように半分ずつ絞り込んで目的の要素を見つける。
中央の要素が探したいデータと一致したときに終了。
一回の比較を行うごとに探索の要素が半分になるので、計算量は__O(log n)__。

参考

開発新卒に捧ぐ、基本のアルゴリズムと計算量 | TECHSCORE BLOG
https://www.techscore.com/blog/2016/08/08/%e9%96%8b%e7%99%ba%e6%96%b0%e5%8d%92%e3%81%ab%e6%8d%a7%e3%81%90%e3%80%81%e5%9f%ba%e6%9c%ac%e3%81%ae%e3%82%a2%e3%83%ab%e3%82%b4%e3%83%aa%e3%82%ba%e3%83%a0%e3%81%a8%e8%a8%88%e7%ae%97%e9%87%8f/