ランダウのO表記法
ランダウの記号（ランダウのきごう、英: Landau symbol）
下記の順で計算量がだんだん上がってくる
$ O(1) 定数時間(constant time)
$ O(\log n) 対数時間(logarithmic time) $ O((\log n)^c) (c \gt1) polylogarithmic
$ O(n) 線形時間(linear time)
$ O(n \log n) 準線形、線形対数時間(linearithmic time, loglinear, quasilinear)
$ O(n^2) 二乗時間(quadratic time)
$ O(n^3) 三乗時間？(cubic time)
$ O(n^{10}) 多項式時間(polynomial time) $ O(2^n) 指数時間(exponential time)
$ O(n!) 階乗時間(factorial time, combinatorial time)
計算量の大小は不等号で表すとこんな感じ。
$ O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(n^{10}) < O(2^n) < O(n!)
各計算量ごとのアルゴリズムなど
$ O(1) 定数時間(constant time)
配列のインデックスアクセス
$ O(\log n) 対数時間(logarithmic time) $ O(n) 線形時間(linear time)
非ソート配列上の探索
$ O(n \log n) 準線形、線形対数時間(linearithmic time, loglinear, quasilinear)
$ O(n^2) 二乗時間(quadratic time)
クイックソート(最悪のとき)
$ O(n^3) ?時間(cubic time)
$ O(n^{c})(c > 1) 多項式時間(polynomial time) $ O(2^n) 指数時間(exponential time)
$ O(n!) 階乗時間(factorial time, combinatorial time)
ネタ枠で$ O(∞) というのもある。
確認用
Q. $ O(\log n) と$ O(n) はどちらの計算量が多いか
Q. $ O(n^{10}) と$ O(2^n) はどちらの計算量が多いか
Q. $ O(n^2) と$ O(n \log n) はどちらの計算量が多いか
参考