📂알고리즘

알고리즘의 비용에 대한 점근적 표기법

정의

크기가 $n$ 인 데이터에 대해 알고리즘의 비용을 다음과 같이 나타낸다.

1. $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\}$$
2. $\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\}$$
3. $\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))$ 를 신경써야할 것이다. 거기서 더 나아가서 로레벨^{low level} 언어 수준의 최적화를 하고 있다면 $\Omega (g(n))$ 까지 고려해야한다.