計算量の表記について

計算量のO表記はなんとなく理解はしていたが、厳密な定義がわかってなくてもやもやしてたので少しまとめる。

アルゴリズムの実行時間は各々の環境によって変わってくるので、コンピュータが実行する命令の数を実行時間とする。また正確な命令の数を把握するのは困難であるので漸近記法またはビッグオー記法で実行時間を見積もる。それらの記法の定義を以下に示す。

$O(f(n))=\{g(n) : あるc>0とn_0が存在し、任意のn\geq n_0についてg(n)\leq c・f(n)を満たす\}$

極限の定義とちょっと似ている。ある関数 $g(n)$ に対して $n$ が十分大きいとき、 $g(n)\leq c・f(n)$ を満たす $f(n)$ が存在するならば $g(n)$ は $O(f(n))$ に属すると言う。ちょっと複雑な関数 $g(n)$ が具体的に与えられたとき、この関数を単純化して表したい。そのときに $g(n)$ をより単純であろう $f(n)$ で表すための記法である。

例えば $O(1)$ に属するのは、 $c・1$ 以下である関数なら何でも良いので定数全部ということになる。
ほかの例として $g(n)=\log n+12$ を考える。このとき

$\begin{align} \log n+12 &\leq \log n+12\log n (n \geq 2のとき)　\\ &\leq 13\log n \end{align}$

となるので $c=13, n_0=2$ とすれば $g(n)$ が $O(\log n)$ の集合に属することがわかる。

参考
sites.google.com

jinyux’s diary

IT業界初心者です。勉強したことをまとめています。

計算量の表記について