【就プロ】計算量 - takahiro_itazuriの公倍数的ブログ

計算量とは何かを説明します。
計算量はアルゴリズムの評価尺度として用いられ、大きく時間計算量と空間計算量に分けられます。

計算量とは入力のデータ量に対してどれくらいのオーダーで計算可能かということを示しています。

時間計算量は主に処理時間の計算量のことを指します。

空間計算量は主にメモリ使用量の計算量のことを指します。

関数$f(n)$に対し、ある定数$a$と$c$が存在してすべての$n > a$に対し$f(n) \leq c \cdot g(n)$となるとき、$f(n)=O(g(n))$と表し、$g(n)$を$f(n)$のオーダーと呼ぶ。

時間計算量について処理時間が短い順に代表的なオーダーについてまとめます。

$O(1)$で表される。処理時間はデータ量に依存しません。

$O(\log{N})$で表される。処理を行うたびに処理対象を何割か減らすことが可能なアルゴリズム。

$O(N^2)$で表される。データ量の分だけ時間がかかります。

$O(N\log{N})$で表される。

$O(N^2)$で表される。二重ループを含むようなアルゴリズム。

$O(k^N)$で表される。要素を取り出す時のすべての組み合わせについて調べるようなアルゴリズム。

$O(N!)$で表される。