Analysis of Algorithms | Asymptotic Notations

읽기 전..

• 향후 상기한 제목으로 작성될 게시물은 모두 Geeks for Geeks Algorithms 페이지들을 번역 및 작성자의 해석대로 정리할 예정입니다.
• 정확한 이론 베이스는 당연히 없고 학습한 내용을 정리할 목적으로 가볍게 작성하였기 때문에 오개념이 있을 수 있으니 혹시 페이지를 방문하신 분들께서는 참고바랍니다.
• 개념을 바로잡기 위한 지적은 언제나 환영이니 부탁드립니다.

Asymptotic Notations(점근적 표기법)

점근적 분석으로 도출된 알고리즘의 복잡도를 표현하기 위해 Θ(세타), Ω(오메가), $O$(빅 오) 3가지 표기법이 있다.

1. Θ Notation

   

   Theta 표기법은 분석하고자 하는 함수를 상계과 하계로 종속시킨다. 위 그래프처럼 함수 $f(n)$을 분석한다고 가정해보자.

   Theta 표기를 가장 간단히 하는 방법은 가장 높은 차수의 변수만 남기고 모두 버린 뒤 해당 변수의 계수도 1로 바꾸면 된다. 이를 테면 $f(n)=3n^3+6n^2+6000$의 Theta 표기법은 $3n^3$이하 변수를 모두 탈락시킨 뒤 계수를 모두 버린 $n^3$이 되므로 완성된 Theta 표기법은 Θ($n^3$)​이다. 가장 높은 차수만을 남기는 이유는 Θ($n^3$)이 Θ($n^2$)보다 커지는 $n_0$지점이 반드시 존재하므로 Θ($n^2$)의 계수가 얼마나 크건 상관없이 누락해도 무방하기 때문이다.

   이를 정리하면 Θ$(g(n))$은 $n_0$이후의 모든 $n$에 대해 $0 \leq c_1\cdot g(n) \leq f(n) \leq c_2\cdot g(n)$를 만족시킬 수 있는 $c_1, c_2, n_0$이 존재하는 모든 함수 $f(n)$의 집합을 의미한다. 즉, $f(n)$이 Θ($g(n)$)에 속한다면 $n \geq n_0$을 만족하는 모든 $n$값에 대해 $f(n)$값은 항상 $c_1 \cdot g(n)$과 $c_2 \cdot g(n)$ 사이에 존재하기 때문에 Θ표기법은 주어진 알고리즘이 아무리 좋거나 나빠지더라도 비교하는 함수 범위 안에 있음을 의미한다.

   참고사항으로 위 정의에 따라 Theta 표기법 상 $n_0 \leq n$을 만족하는 모든 $n$에 대해 $f(n)$값은 반드시 $f(n_0)$보다 커야한다.

2. Big O Notation

   

   Big O 표기법은 알고리즘의 상계만을 다룬다. 예를 들어 Insertion 정렬의 경우 최상의 경우에 $n$만큼의 시간이 소요되고 최악의 경우 $n^2$만큼 소요되는데 이를 Big O 표기법으로 나타내면 $O(n^2)$이다. 그리고 Big O 표기법에 따라 최상의 경우($n$시간 소요)도 포함한다. 얼핏 Θ표기법과 차이점이 없어보이지만 Θ표기법은 최상의 경우[Θ($n$)]와 최악의 경우[Θ($n^2$)]를 따로 표기해야 한다.

   하계에 대해 고려할 필요가 없기 때문에 상계에 대한 정보만 가지고 있을 때 유용하게 사용할 수 있다. 그리고 많은 알고리즘들은 단순하게 상계에 대해 파악할 수 있기 때문에 일반적인 시간복잡도를 논할 땐 Big O 표기법을 사용한다.

   이를 정리하면 상수 $n_0$보다 큰 모든 수 $n$에 대해 $0 \leq f(n) \leq c \cdot g(n)$을 만족하는 양수의 값 $c$와 $n_0$가 존재하는 모든 함수 $f(n)$의 집합을 $O(g(n))$이라 표현할 수 있으므로 Big O 표기법은 주어진 알고리즘 $f(n)$이 아무리 나빠도 비교하는 함수 $c \cdot g(n)$보다는 같거나 좋음을 나타낸다.

3. Ω Notation

   Big O 표기법이 점근적 상계에 대한 정보만을 제공했다면 Ω표기법은 점근적 하계만을 다룬다. 그러나 점근적 하계는 최상의 케이스를 의미하므로 일반적으로 잘 쓰이지 않는다.

   

   Ω($g(n))$)은 상수 $n_0$보다 큰 모든 수 $n$에 대해 $0 \leq c \cdot g(n) \leq f(n)$을 만족하는 양수의 값 $c$와 $n_0$가 존재하는 모든 함수 $f(n)$의 집합을 의미하므로 Ω 표기법은 주어진 알고리즘 $f(n)$이 아무리 좋아도 비교하는 함수 $c \cdot g(n)$보다는 같거나 나쁨을 나타낸다.

   예를 들어, 위에서 기술하였듯이 Insertion Sort의 시간 복잡도는 최악의 경우 $n^2$이고 최상의 경우 $n$이므로 Ω 표기법으로 나타내면 Ω(n)이 된다. 하지만 우리는 알고리즘의 평균적인 상황이나 최악의 상황에서의 성능을 요구하기에 그닥 쓸모있는 정보를 제공하진 않는다.

알고리즘 문제를 해결하는 상황에선 보통 Big case를 주는 경우가 많기에 worst case를 고려하지 않으면 TLE(Time Limit Exceeded)문제가 발생한다. 그리고 input의 공간적 분포를 따졌을 때 대다수는 average case이므로 사용하고자 하는 알고리즘의 시간복잡도를 잘 따져봐야 한다.

반대로 Small case가 주어졌지만 수행시간도 극단적으로 짧게 제공된다면 asymptotic 관점에서는 느리지만 실제로는 더 빠른 알고리즘을 사용하는 융통성이 필요할지도 모르겠다. 주어진 input이 n_0보다 작다던지...

게시물 출처: Analysis of Algorithms | Set 3 (Asymptotic Notations)