[計算量をざっくり理解] Big O 記法

ランダウの記号

ランダウの記号（ランダウのきごう、英: Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

“Big O notation” とも呼ばれます。

入力サイズの変化による計算量の変化を用いて、アルゴリズムを分類するために使われます。

無限大での関数のふるまいを以下の二つの考え方に従いざっくりと考えます。

1．影響力の一番強い項だけを考える。
2．係数は無視する。

例えば，$n^2+2n$であれば、ルール1により$n^2$となり$O(n^2)$と書かれ、「$n^2$のオーダーである」と言われます。

また、$2n \log n$ は、ルール2により$n \log n $ となり$O(n \log n) $と書かれ、「$n \log n$のオーダーである」と言われます。

厳密には以下のように定義されます。

$$ \exists x_0 , \exists C \gt 0 \mbox{ s.t. } x \gt x_0 \Rightarrow |f(x)| \leq C|g(x)| $$

下の図がざっくりと理解しやすいです。

「$ f(x) $ は漸近的に $ g(x) $ によって上からおさえられる」ことを意味します。

また、このことは、「上界 (upper bound) 」という言葉を用いることで、「関数$ g(x) $が関数$ f(x) $の上界である」と表現されます。