プログラムの計算量を表すO記法について、使用例を調査しました。
計算量（オーダー）とは？
あるアルゴリズムを使った演算の性能を表す指標。
計算量は大きく二つに分けられる。
- 時間計算量（処理時間の計算量）
- 空間計算量（メモリ使用量の計算量）
単に計算量（オーダー）と言った場合、時間計算量のことを指す。
O記法（オーダー記法）
特定のアルゴリズムでの計算が、どれくらい掛かるかを表した記号。
処理対象のデータが非常に大きくなった時の処理時間を大雑把に評価する。
処理時間が短い順（性能が良い順）に代表的なオーダーをまとめる。
| 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の階乗に比例した時間。 |
巡回セールスマン問題の総当たりによる解法 |
計算量のめやす
（多項式オーダーの世界）
O(1)，O(logn)，O(n)，O(nlogn)，O(n^2)，O(n^3)，O(n^100)
ーーー越えられない壁ーーー
O(2^n)，O(n!)
参考元
プログラムの計算量オーダーとは？英語で何という？
https://4engineer.net/cs/complexity/
一週間で身につくアルゴリズムとデータ構造|応用編第1日目：アルゴリズムと計算量
http://sevendays-study.com/algorithm/ex-day1.html
時間計算量とは - IT用語辞典
http://e-words.jp/w/%E6%99%82%E9%96%93%E8%A8%88%E7%AE%97%E9%87%8F.html
空間計算量とは - IT用語辞典
http://e-words.jp/w/%E7%A9%BA%E9%96%93%E8%A8%88%E7%AE%97%E9%87%8F.html
オーダー記法・その1：使用例からの導入 - あざらしとペンギンの問題
http://azapen6.hatenablog.com/entry/2013/02/04/214644
計算量を具体的に見てみる - きしだのはてな
http://d.hatena.ne.jp/nowokay/20090106
オーダー記法の定義と大雑把な意味 | 高校数学の美しい物語
http://mathtrain.jp/landausymbol
時間計算量 - cppreference.com
http://ja.cppreference.com/w/cpp/complexity
[初心者向け] プログラムの計算量を求める方法 - Qiita
http://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c
ランダウの記号 - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7
参考書籍
ゲームプログラマになる前に覚えておきたい技術 (P.486)
https://www.amazon.co.jp/%E3%82%B2%E3%83%BC%E3%83%A0%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AB%E3%81%AA%E3%82%8B%E5%89%8D%E3%81%AB%E8%A6%9A%E3%81%88%E3%81%A6%E3%81%8A%E3%81%8D%E3%81%9F%E3%81%84%E6%8A%80%E8%A1%93-%E5%B9%B3%E5%B1%B1-%E5%B0%9A/dp/4798021180