特定のアルゴリズムでの計算が、どれくらい掛かるかを表した記号。
処理対象のデータが非常に大きくなった時の処理時間を大雑把に評価する。
処理時間が短い順（性能が良い順）に代表的なオーダーをまとめる。
| O記法 | 概要 | 使用例 |
|---|---|---|
| O(1) | **<定数時間>** 処理時間がデータ量に依存しない。必ず一発で取得できる。 | 配列要素へのアクセス、ハッシュテーブルによるデータ検索、連結リストへの追加/削除 |
| O(logN) | **<対数時間>** 処理をひとつ行うたびに処理対象を何割か減らせるようなアルゴリズム。データ量が増えても計算時間がほとんど増えない。多くの場合、これ以上の改善はする必要はない。 | ソート済み配列の二分探索 |
| O(N) | **<線形時間>** データ量の分だけ時間がかかる。forループ１回分。N回もしくはNに比例する回数以内のループで処理が終わる場合。 | 非ソート配列の探索 |
| O(NlogN) | **<準線形、線形対数時間>** ちょっと重いO(N)程度。マージソートのように二分木でデータを分割し、かつそれらをリニアサーチするようなアルゴリズムの計算量。二分木のオーダー(logN)×リニアサーチのオーダー(N)をかけあわせてNlogNになる。 | クイックソート、マージソート、ヒープソート |
| O(N^2) | **<二乗時間>** 要素からすべての組み合わせのペアについて調べるようなアルゴリズム。工夫しないソート処理など。二重のforループ。これ以上は処理が遅すぎて使いにくい。 | 挿入ソート、バブルソート、選択ソート、シェルソート |
| O(N^3) | **<多項式時間>** 三重ループを伴う配列全体の走査。 | 行列計算 |
| O(k^N) | **<指数時間>** 要素を取り出すときのすべての組み合わせについて調べるようなアルゴリズム。N軒の家をどの順序で回ったら最短距離になるか。 | ルービックキューブの総当たりによる解法 |
| O(N!) | **<階乗時間>** Nの階乗に比例した時間。 | 巡回セールスマン問題の総当たりによる解法 |
参照：https://qiita.com/asksaito/items/59e0d48408f1eab081b5
コメント