Complexity Analysis (2) - Asymptotic Analysis (점근적 분석)

서문 (Preface)

지난 포스팅에서는 알고리즘의 정의와, 효율성을 분석하는 방법, 그리고 알고리즘의 복잡도를 시간과 공간적인 측면에서 수학적으로 기술할 수 있다는 것에 대해 알아봤습니다. 그리고 이번 포스팅에서의 주제는 이걸 확장시켜서 구체적으로 어떤 방법을 통해 복잡도를 기술할 수 있는지를 다루도록 하겠습니다.

 

복잡도의 점근적 분석 (Asymptotic Analysis)

점근적 분석이란, 자료의 갯수 \( n \) 값이 커질수록 이에 따라 \( n \) 에 관한 어떤 알고리즘의 복잡도가 어떤식으로 변화해 나가는지를 의미합니다. 이 때, 충분히 큰 \( n \) 에 대하여 주어진 \( n \) 에 관한 함수 \( f(n) \) 을 또 다른 함수 \( g(n) \) 을 통하여 나타낼 수 있는데, (\( g(n) \) 을 \( f(n) \) 과 충분히 비슷한 함수라고 가정합시다) 구체적으로는:

$$ f(n) \sim g(n) \; (n \geq n_{0}, \; n \rightarrow \infty) $$

 

해석을 하자면, \( n_{0} \) 이상인 모든 \( n \) 에 대하여 (충분히 큰 \( n \)), \( n \) 이 증가함에 따라 \( f(n) \) 값이 \( g(n) \) 에 근접해간다는 뜻입니다. 이때 \( \sim \) 를 좀더 정확하게 기술하면:

$$ \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1 \; (\forall n \geqslant n_{0}) $$

 

즉, 충분히 큰 \( n \) 이 무한히 증가함에 따라 두 함수의 함숫값의 격차가 1에 수렴한다는 뜻이죠. (같아진다는 말입니다)

 

예를들어 보자면, 충분히 큰 $ n $ 값에 대해, \( n \) 이 증가함에 따라  \( f(n) = 10n^{3} - 100n \) 과 \( g(n) = n^{3} \) 의 격차가 점점 줄어들어 1에 가까워지는 것을 것을 알 수 있습니다.

 

Big-O Notation (Big-O 표기법)

위에 서술한 내용을 좀 더 간단히 표현하기 위해 수학자들은 몇가지의 표기법을 도입했는데요, 그 중 제일 대표적인 것이 바로 Big-O 표기법입니다. 이번 주제는 직관적인 설명을 위해 좀 더 예시를 통해 설명을 하겠습니다.\( n \) 에 관한 두 함수 \( f(n) = 5n^{3} - 20n^{2} - 10n + 5 \) 와 \( g(n) = n^3 \) 이 있을 때, 이 두 함수의 그래프는 아래와 같이 그려집니다 (파란색이 \( f \), 빨간색이 \( g \) 입니다):

figure 1. 두 함수 f, g 의 그래프

 

이 때, 두 함수는 결국 비슷한 증가 양상 (Trend) 을 보이므로 (다항함수이기 때문에 최고차항이 결국 전체 결과값을 지배하게 됩니다) 함수 \( g \) 에 어떤 상수 \( c \) 를 곱하게 되면 충분히 큰 \( n \) 값에 대하여, \( g(n) \) 값을 \( f(n) \) 이상으로 만들 수 있습니다. 위 두 함수의 경우에는 이때 이 \( c \) 값을 5로 두면, \( n \) 이 대략적으로 2 이상일 때 (이 때의 \( n \) 값을 \( n_{0} \) 라고 표현합니다), \( g(n) \) 은 아래와 같이 \( f(n) \) 보다 커지게 됩니다:

figure 2. 함수 f 보다 커지는 g

 

다시 말해, 어떤 함수 \( f(n) \) 이 주어져 있을 때, 비슷한 증가 양상을 보이는 함수 \( g(n) \) 를 정의 내릴 수 있고, 이 때 어떤 상수 \( c \) 가 정의되면, 충분히 큰 \( n \) 값에 대하여 \( c \cdot g(n) \) 이 \( f(n) \) 보다 크거나 같을 때, \( f(n) = O(g(n)) \) 이라고 표기합니다.

 $$ f(n) = O(g(n)) \; \Leftrightarrow  \; \exists c \; : \; f(n) \leqslant c \cdot g(n) \; (\forall n \geqslant n_{0}) $$

 

그래서 무슨 뜻인데?

자 수학 기호가 많이 등장을 해서 순간 당황하셨을 거라 생각합니다. 그렇지만 위의 식을 하나하나 뜯어보면 이해하는게 크게 어렵지 않다는걸 알 수 있습니다. 다시 말해:

\( n \) 에 관한 두 함수 \( f \) 와 \( g \) 가 정의될 때, 충분히 큰 모든 \( n \) 에 대하여  (\( n \geqslant n_{0} \))
\( cg(n) \) 을 항상 \( f(n) \) 보다 크거나 같게 만드는 어떤 상수 \( c \) 가 존재하면,
이 때 \( f(n) \) 을 \( O(g(n)) \) 이라 표기한다.

 

자 그러면 위의 예시로 돌아가서 대입을 해봅시다. \( f(n) \) 을 \( f(n) = 5n^{3} - 20n^{2} - 10n + 5 \)  로, \( g(n) \) 을 \( g(n) = n^3 \) 로 정의 했었고, 위의 조건을 만족하는 \( c \) 값 이 존재하므로, 각각 대입하면: \( 5n^{3} - 20n^{2} - 10n + 5 = O(n^{3}) \) 이 나오게 됩니다.

이 때, \( f(n) \) 을 어떤 알고리즘 A 의 시간 복잡도라고 생각하면, 이 알고리즘의 시간 복잡도는 \( O(n^{3}) \) 이라고 기술할 수 있게 되는거죠.

결국 위 과정을 통해 저희가 얻어낸 것은 복잡한 함수로 정의되는 알고리즘의 복잡도를 중요하지 않은 부분을 생략해서 단순화 시켜 나타낼 수 있다는 말인 것이죠. 이를 통해 서로 다른 알고리즘들의 복잡도가 Big-O 를 이용해 같은 함수로 표현될 수 있다면, 이 둘의 "복잡도가 같다, 즉 효율성이 같다" (혹은 비슷하다) 라고 정의를 내릴 수가 있게됩니다.

 

다항함수 (Polynomial Functions) 의 복잡도의 Big-O 표현

앞으로의 편의를 위해 좀 더 일반화를 해봅시다. 단순히 위에서 본 \( n^{3} \) 뿐만 아니라 위 방식을 최고차항을 어떤 실수 \( k \) 로 갖는 모든 다항함수에 적용시킬 수 있지 않을까요?

 

아래와 같이 일반화된 형태의 최고차항이 \( k \) 인 다항함수 \( T(n) \) 이 주어질 때:$$ T(n) = a_{k}n^{k} + a_{k-1}n^{k-1} + \cdots + a_{1}n + a_{0} = \sum_{i=0}^{k} a_{i}n^{i} $$

 

이 충분히 큰 \( n \geqslant n_{0} \) 에 대하여 \( T(n) \leqslant cn^{k} \) 를 성립시키는 상수 \( c \) 값을 찾을 수 있으므로, (엄밀한 증명을 원한다면 proof by contradiction 을 이용해봅시다. 즉, c 값이 존재하지 않는다고 가정하면 단순하게는 어떤 \( n \) 과 \( c \) 를 찾아서 이 역이 성립하지 않음을 증명할 수 있겠죠) \( T(n) = O(n^{k}) \) 가 성립하죠. 따라서, 이 \( T(n) \) 형태의 시간 복잡도를 갖는 어떤 알고리즘이든 전부 \( O(n^{k}) \) 의 시간 복잡도를 갖는다고 표현할 수 있다는 뜻입니다.

(즉, 앞으로 나오는 알고리즘들에서 다항함수 형태의 복잡도를 가질 때, 저희는 Big-O 를 이용해 단순화된 표기를 할 수 있다는 말이죠)

위의 일반화와 비슷한 방식을 다른 형태의 함수 (지수, 로그 등) 에도 적용시킬 수 있습니다. 해당 케이스들은 다음에 다루도록 하겠으나 궁금하다면 직접 찾아보거나 증명을 해보는 것도 좋은 방법입니다.

 

기타 Big-O 의 성질

\( n \) 에 대한 함수 \( f_{1}, f_{2}, g_{1}, g_{2} \) 에 대하여 \( f_{1}(n) = O(g_{1}(n)) \) 이고, \( f_{2}(n) = O(g_{2}(n)) \) 일때, 다음이 성립합니다:

$$ f_{1}(n) \cdot f_{2}(n) = O(g_{1}(n) \cdot g_{2}(n)) $$

(즉, 두 함수의 곱에 Big-O 를 씌우면 각각의 Big-O 로 bounded 되는 함수들의 곱에 Big-O 를 씌운 것과 같습니다.)

$$ f_{1}(n) + f_{2}(n) = O(max(g_{1}(n), g_{2}(n))) $$

(두 함수를 합한 것의 Big-O 표현은 두 함수의 Big-O bounding 함수 중 큰 것에 Big-O 표현과 같습니다)

 

또, \( n \) 에 대한 함수 \( f \) 에 대하여 이 함수의 상수곱은 이 함수의 Big-O 표현에 영향을 주지 않습니다:

$$ f(n) = O(g(n)) \Rightarrow k \cdot f(n) = O(k \cdot g(n)) = O(g(n)) $$

 

이외의 Approximation (근사) 표현

Big-O 표현은 어떤 함수의 upper bound (즉, \( f \) 가 \( g \) 의 상수곱보다 항상 작거나 같아야 한다는 것을 명시함으로써, \( f \) 의 증가 양상이 항상 \( g \) 와 동일해야 한다는 것을 명시) 를 기술한다면, Big-O 외에도 아래와 같은 다양한 근사치를 나타내기 위한 표현들이 존재합니다:

 

Big-Omega Notation (Big-Omega 표기법)

오메가의 경우에는 Big-O 와 반대로 어떤 함수의 lower bound 를 알려주는 표현입니다. 즉, 두 함수 \( f \) 와 \( g \) 가 주어질 때, 충분히 큰 모든 \( n \) 값에 대하여 항상 \( f(n) \geqslant c \cdot g(n) \) 이 성립된다면 (\( f \) 가 항상 \( g \) 의 증가 양상 이상이라면) \( f(n) = \Omega(g(n)) \) 이라 표기할 수 있습니다.

 $$ f(n) = \Omega(g(n)) \; \Leftrightarrow  \; \exists c \; : \; f(n) \geqslant cg(n) \; (\forall n \geqslant n_{0}) $$

 

Theta Notation (Theta 표기법)

마지막으로, theta 의 경우에는 어떤 함수의 증가 양상이 충분히 큰 모든 \( n \) 값에 대하여 항상 다른 어떤 함수와 같아야 한다는 걸 표시합니다. 즉, 두 \( n \) 에 관한 함수 \( f \) 와 \( g \) 가 있을 때, 충분히 큰 \( n \) 값에 대해 \( f(n) = O(g(n)) \) 이고 동시에 \( f(n) = \Omega(g(n)) \) 을 만족한다면, 이 \( f \) 의 증가 양상을 theta 를 통해 \( f(n) = \theta(g(n)) \) 이라고 표현할 수 있습니다.

 $$ f(n) = \theta(g(n)) \; \Leftrightarrow  \; \exists c_{1}, c_{2} \; : \; f(n) \geqslant c_{1} \cdot g(n) \wedge f(n) \leqslant c_{2} \cdot g(n) \; (\forall n \geqslant n_{0}) $$

 

요약 (Summary)

이번 포스팅에서는 새로운 수학적 표현들이 많이 등장해 살짝 당황스러우셨을수도 있을 것 같습니다. 그렇지만 지난번에도 언급했듯 수식은 결국 위의 정의한 내용들과 같은 말을 하는 것 뿐이니 앞으로 알고리즘을 분석하는데에 있어 Big-O, Big-Omega, 그리고 Theta 표기법이 어떤 뜻인지, 대략적으로만 이해하셔도 충분합니다. 그럼 다음 시간에는 좀 더 다양한 함수들로 표현되는 알고리즘의 복잡도와 예제들을 중점적으로 알아보도록 하겠습니다.