[알고리즘] 시간 복잡도 Big - O, Big - Ω, Big - θ

[알고리즘] 시간 복잡도 Big - O, Big - Ω, Big - θ

 

알고리즘의 분석에 사용되는 대표적인 점근적 표기법으로 Big - O, Big - Ω, Big - θ 세 가지가 있습니다.

이번 포스팅에서는 이 세 가지의 점근적 표기법에 대하여 알아보겠습니다.

 

다음 교재를 참고하여 작성함을 미리 밝힙니다. 

한빛아카데미 - 쉽게 배우는 알고리즘

---

• Big - O

Big - O는 함수의 점근적 상한을 나타냅니다.

정의 
$$O(g(n)) = \{f(n)| \exists c>0, n_0 > 0 \mbox{  Subject to  } \forall n \geq n_0, f(n) \leq cg(n)\}$$

식을 해석해보면 "충분히 큰 모든 $n$에 대하여 $f(n) \leq cg(n)$인 양의 상수 $c$가 존재한다." 입니다.

 

예를 들어 $f(n) = 5n^3$이면 $c \geq 5$에 대하여 $cn^3 \geq 5n^3$이기 때문에 $g(n) = n^3$입니다.

따라서 $f(n) = 5n^3$은 $O(g(n)) = O(n^3)$에 속합니다. 

 

 

Big - O 예제 1.

$5n^2 = O(n^2)$임을 보여라.

>> $c = 6$으로 잡고 적당한 $n_0$를 찾아내면 됩니다. $\forall n\geq0$에 대하여 $5n^2 \leq 6n^2$이 성립하므로 $5n^2 \in O(n^2)$입니다.

 

 

Big - O 예제 2.

$5n^2 + 3 = O(n^2)$임을 보여라.

>> $c = 6$으로 잡고 적당한 $n_0$를 찾기 위해 $5n^2 + 3 \leq 6n^2$을 풀면 $\sqrt{3} \leq n$입니다. 따라서 $n_0 = 2$로 설정하면 충분합니다. $\forall n \geq 2$에 대하여 $ 5n^2 + 3 \leq 6n^2$을 만족하므로 $5n^2 + 3 \in O(n^2)$입니다.

---

• Big - Ω

Big - Ω는 함수의 점근적 하한을 나타냅니다.

 

정의
$$\Omega(g(n)) = \{f(n) | \exists c > 0, n_0 > 0 \mbox{  Subject to  } \forall n \geq n_0, f(n) \geq c g(n)\}$$

식을 해석해보면 "충분히 큰 모든 $n$에 대하여 $f(n) \geq cg(n)$인 양의 상수 $c$가 존재한다." 입니다.

즉, $\Omega(g(n))$은 충분히 큰 $n$에 대하여 $g(n)$에 적당한 상수를 곱해서 $f(n) \geq c g(n)$을 만족하면 됩니다.

 

예를 들어 $f(n) = 5n^3$이라고 하면 $c \leq 5$에 대하여 $5n^3 \geq cn^3$을 만족하므로 $g(n) = n^3$입니다.

따라서 $f(n) = 5n^3 \in \Omega(n^3)$ 입니다.

 

Big - Ω 예제 1.

$5n^2 = \Omega(n^2)$임을 보여라.

>> $c = 4$로 설정을 하고 적당한 $n_0$를 찾으면 됩니다. $5n^2 \geq 4n^2$는 $n \geq 0$에서 만족합니다.

따라서 $5n^2 \in \Omega(n^2)$ 입니다.

---

• Big - θ

Big - θ는 함수의 점근적 상한과 하한 즉, O 와 Ω를 모두 만족하는 경우를 의미합니다.

정의
$$\Theta(g(n)) = O(g(n)) \cap \Omega(g(n))$$

정리해보면 "충분히 큰 모든$n$에 대하여 $c_1 g(n) \leq f(n) \leq c_2 g(n)$인 양의 상수 $c_1, c_2$가 존재한다." 입니다.

 

예를 들어 $5n^3 \in O(n^3)$이고, $5n^3 \in \Omega(n^3)$이므로 $5n^3 \in \Theta(n^3)$ 입니다.