アルゴリズムのコストに関する漸近記法
定義
大きさが$n$のデータに対するアルゴリズムのコストを次のように表示する。
- $O$表記: $$ O(g(n)) := \left\{ f(n) \ | \ \exists c > 0, n_{0} \in \mathbb{N} : \forall n \ge n_{0} \implies f(n) \le c g(n) \right\} $$
- $\Omega$表記: $$ \Omega (g(n)) := \left\{ f(n) \ | \ \exists c > 0, n_{0} \in \mathbb{N} : \forall n \ge n_{0} \implies f(n) \ge c g(n) \right\} $$
- $\Theta$表記: $$ \Theta (g(n)) := O (g(n)) \cap \Omega (g(n)) $$
説明
漸近記法は、アルゴリズムのコストを数学的に表すものだ。エプシロン-デルタ論法を理解していれば、特に難しくなく、自然な定義として受け入れられるだろう。さらに直感的な説明を加えると、以下のようになる:
- $O(g(n))$は、アルゴリズムが消費することができる最大-最悪のコストである。
- $\Omega (g(n))$は、アルゴリズムが消費することができる最小-最善のコストである。
- $\Theta (g(n))$は、アルゴリズムが消費する平均コストである。
これらは集合であるため、$7n^3 \in O (n^3)$のように表されるのが正しいが、通常は便宜上$7n^3 = O (n^3)$のような表現を使う。また、$O(n^3) \subset O(n)$であるため、数式展開上、$O(n^3) + O(n) = O(n^3)$のような表現も見られる。これを直感的な言葉で説明すると、「とにかく$O(n^3)$ほどの莫大なコストがかかるなら$O(n)$ぐらいは問題ないから$O(n^3)$に含まれても構わない」という感じになる。
数学者の立場からすると、最も興味があるのは、コストの限界を定める$O(g(n))$だろう。一方で、適切にアルゴリズムを使用する必要があるエンジニアの立場からは、実際のコストを表す$\Theta (g(n))$を気にすべきだ。さらに進んで、ローレベルの言語レベルでの最適化を行っているなら、$\Omega (g(n))$も考慮しなければならない。