점근적 표기법 (Asymptotic Notation)

 

내가 구현한 알고리즘이 한 컴퓨터에서 0.1초만에 실행되지만, 다른 컴퓨터에서는 0.3초가 걸렸다면 무엇을 기준으로 알고리즘의 성능을 파악해야 할까요? 오늘은 이런 상황에서 사용할 수 있는 점근적 표기법 $($Asymptotic Notation$)$ 에 대해 알아보도록 하겠습니다.

---

#️⃣ 점근적 표기법이란?

알고리즘을 공부하면 가장 초반에 배우게 되는 개념인 점근적 표기법은 쉽게 말하면 구현한 알고리즘의 성능을 알아볼 수 있는 방법입니다. $Big-O(빅\;오), Big- Ω(빅 \; 오메가), Big- Θ(빅 \; 세타)$와 같이 표현되며, 실행 환경에 관계없이 수학적인 표현을 통해 알고리즘의 성능을 표현할 수 있도록 해줍니다.

 

이 때, 함수가 복잡할수록 비교가 어려워지기 때문에 함수를 단순화하게 되는데요, 중요하지 않은 부분과 상수 계수를 제거하게 됩니다.

 

예를 들어 다음과 같은 $ f(n)=n^{3}+2(n^{2}-1)-n+10 $ 함수에서 n의 값이 무한히 증가한다고 가정했을 때, 가장 영향력이 큰 부분은 $ n^{3} $ 부분입니다. 따라서 나머지는 전부 무시하고, 가장 높은 차수인 n의 3승 항만 가지고 판단하게 됩니다. 만약 $ 2n^{3} $ 와 같이 상수가 붙어 있는 경우, 상수도 무시하게 됩니다.

 

 

💠빅 오 표기법

$Big-O$ 빅 오 표기법은 가장 많이 사용되는 표기법으로, 최악의 시간 복잡도를 나타내는데 사용됩니다. 최악의 경우에도 이것보다는 실행 시간이 빠르다는 것을 나타냅니다.

 

$O$는 가장 높은 차수보다 같거나 높은 식을 뜻합니다. 즉 $ n^{2}+n+1 $ 과 같은 식이 있을 때, 가장 높은 차수는 $ n^{2} $이므로 $ O(n^{2}) $ 로 사용합니다. 이 때, $ O(n^{3}), O(n^{4}) $ 등 차수가 더 큰 식을 사용해도 맞는 말이지만 보통 주어진 식에서의 가장 높은 차수를 사용합니다.

 

표현식은 다음과 같습니다.

$$ n^{2}+n+1 = O(n^{2}) $$

 

만약 다음과 같은 $ f(n) = n^{2}+n+1,\;g(n) = n^{4}+n^{3} $ 두 개의 식이 있다면,  $f(n) = O(g(n))$ 과 같이 사용할 수 있는데요, 이는 $f(n)$의 차수가 $g(n)$의 차수보다 같거나 작다는 의미입니다.

 

 

💠빅 오메가 표기법

$Big-\Omega $ 빅 오메가 표기법은 최선의 시간 복잡도를 나타내는데 사용됩니다. 알고리즘이 아무리 빨라도 이것보다는 실행 시간이 느리다는 것을 나타냅니다.

 

$\Omega$는 가장 높은 차수보다 같거나 낮은 식을 뜻합니다. 즉 $ n^{2}+n+1 $ 과 같은 식이 있을 때, 가장 높은 차수는 $ n^{2} $이므로 $ \Omega(n^{2}) $ 로 사용합니다. 이 때, $ \Omega(n), \Omega(logn) $ 등 차수가 더 낮은 식도 전부 맞는 말이 됩니다.

표현식은 다음과 같습니다.

$$ n^{2}+n+1 = \Omega(n^{2}) $$

 

만약 다음과 같은 $ f(n) = n^{2}+n+1,\;g(n) = n-5 $ 두 개의 식이 있다면,  $ f(n) = \Omega(g(n)) $ 과 같이 사용할 수 있는데요, 이는 $f(n)$의 차수가 $g(n)$의 차수보다 같거나 크다는 의미입니다.

 

 

💠빅 세타 표기법

$Big-\Theta$ 빅 세타 표기법은 알고리즘이 최선 또는 최악의 시간복잡도를 가지더라도 어떠한 범위 내에 있다는 것을 나타내는데 사용합니다. 쉽게 말하면 함수의 최고차항이라고 생각하면 됩니다.

 

$\Theta$는 최고차항$($가장 높은 차수$)$를 뜻합니다. 즉 $ n^{2}+n+1 $ 과 같은 식이 있을 때, 가장 높은 차수는 $ n^{2} $이므로 $ \Theta(n^{2}) $ 로 사용합니다. 

표현식은 다음과 같습니다.

$$ n^{2}+n+1 = \Theta(n^{2}) $$

 

만약 다음과 같은 $ f(n) = n^{2}+n+1,\;g(n) = n^{2}-5 $ 두 개의 식이 있다면,  $ f(n) = \Theta(g(n)) $ 과 같이 사용할 수 있는데요, 이는 $f(n)$의 최고차항이 $g(n)$의 최고차항과 같다는 의미입니다.

 

$f(n)$의 복잡도가 어떠한 상황에서도 $g(n)$의 범위 내에 있다는 뜻인데요, 조금 자세히 알아보자면 빅 세타 표기법의 정확한 정의는 '$n \geq n_{0}$인 모든 $n$에 대해 $0\leq c_{1}g(n) \leq f(n) \leq c_{2}g(n)$을 만족하는 양의 상수 $c_{1}, c_{2}, n_{0}$이 존재한다' 입니다. 이를 그래프로 나타내면 다음과 같습니다.

 

 

---