ランダウのO表記法
ランダウの記号（ランダウのきごう、英: Landau symbol）
下記の順で計算量がだんだん上がってくる
$ O(1) 定数時間(constant time)
$ O(\log^* n) 反復対数時間(iterated logarithmic time) $ O(\log n) 対数時間(logarithmic time) $ O((\log n)^c)\quad (c \gt1) 多対数的時間？(polylogarithmic 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^{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) 入力が段階的に半分になるようなものはここに分類されやすい？
$ n=1024 約10回
$ n=1,048,576 約20回
例:
$ O(n) 線形時間(linear time)
実行時間が入力サイズに比例して増加
例:
非ソート配列上の探索
$ O(n \log n) 準線形、線形対数時間(linearithmic time, loglinear, quasilinear)
n回の処理をしつつ、各回で$ \log n の探索や分割を行う
$ n=1000 約10000回
$ n=1000000 約2000万回
例:
$ O(n^2) 二乗時間(quadratic time)
入力全体に対して、さらに入力全体を回す
二重ループ
$ n=1000 約100万回
$ n=1000000 約1兆回
例:
クイックソート(最悪のとき)
$ O(n^3) ?時間(cubic time)
$ O(n^{c})\quad(c > 1) 多項式時間(polynomial time) $ O(2^n) 指数時間(exponential time)
実行時間が入力サイズの追加ごとに倍増
$ n=10 1024回
$ n=20 約100万回(1048576回)
$ n=30 約10億回
$ n=100 約$ 10^{30} 回
例:
集合のすべての部分集合を生成
$ O(n!) 階乗時間(factorial time, combinatorial time)
実行時間が入力サイズの階乗に比例
$ 10! 約360万回
$ 20! 約$ 2.4\times10^{18} 回
例:
集合のすべての順列生成
ネタ枠で$ O(∞) というのもある。
確認用
Q. $ O(\log n) と$ O(n) はどちらの計算量が多いか
Q. $ O(n^{10}) と$ O(2^n) はどちらの計算量が多いか
Q. $ O(n^2) と$ O(n \log n) はどちらの計算量が多いか
参考