경북대 COMP0319 강의 기반의 정리
Introduction to algorithms 3판 참고

Order or Growth

지난 시간에 정렬 문제를 해결하기 위해 삽입 정렬과 병합 정렬, 2개를 알아보았다. 삽입 정렬은 최악의 경우 $an^2 + bn + c$의 계산시간이, 병합 정렬은 $c_1n \log n + c_2n$임을 알아보았다. 병합 정렬의 최악의 경우에 $T(n)$을 알아보기 위해 Order of Growth라는 방법을 적용해보자.

삽입 정렬

삽입 정렬에서 각 code line마다 소모되는 비용 $c_1, c_2, ...$를 간단히 하기 위해 $T(n) = an^2 + bn + c$로 표기하였는데 더 간단한 방법이 바로 Order of Growth이다. 이 방법은 우리가 실제 관심있는 실행시간에 영향을 주는 요소들에 더 집중한다. 그게 바로 차수가 가장 큰 항이다. 삽입 정렬의 경우에는 $an^2$이 된다. 가장 차수가 큰 항만을 고려하는 이유는 차수가 더 작은 항들은 상대적으로 총 실행시간에 영향을 덜 미치기 때문이다. 또한 여기서 큰 input에 대해서는 계수도 영향도가 낮기에 계수도 무시한다. 그럼 최종적으로 삽입 정렬의 worst case의 경우 $T(n)$은 $n^2$이 된다. 이를 이제 $\Theta (n^2)$라 하자.

병합 정렬

병합 정렬의 경우 문제의 크기가 $n \le c$로 충분히 작다면, $T(n)$은 상수로 나타내지게 된다. 그러므로 Order of Growth를 적용하면 $\Theta(1)$로 표현할 수 있다.
이제 $n > 1$의 경우를 따져보자. 이 때 병합 정렬은 문제의 크기를 2개로 나누고 나눈 문제의 크기는 2배 줄인다는 것을 배웠다. 또한 여기에 나누는데 소모되는 비용(divide), $D(n)$과 합치는데 소모되는 비용(combine), $C(n)$을 더하게 되면 $T(n)$은 $T(n) = 2T(n/2) + D(n) + C(n)$이다. 여기에 Order of Growth를 적용하면 최종적으로 병합 정렬의 $T(n)$은 다음과 같다.

즉 최악의 경우 병합 정렬의 경우 이전에 배운 재귀 트리를 사용하면 $T(n) = \Theta(n\log n)$이 된다. 그러므로 우리는 병합 정렬이 삽입 정렬보다 알고리즘의 효율성이 높다고 할 수 있다.

점근적 표기법(Asymptotic Notation)

Order of Growth를 통해 알고리즘의 효율성을 간략하게 확인할 수 있고 이를 통해 우리는 어떤 알고리즘이 상대적으로 더 효율적인지를 파악할 수 있다. 점근적 표기법은 Order of Growth처럼 큰 크기의 문제 사이즈 $n$에 대한 알고리즘의 효율성을 따지는 방법이다. 즉, 입력의 크기가 한계 없이 증가함에 따라 알고리즘의 실행 시간이 어떻게 증가되는지 확인할 수 있다. 이 말은 점근적 표기법을 통해 알고리즘의 효율성을 따지면, 아주 작은 크기를 제외한 모든 입력에 대해 점근적으로 더 큰 효율적인 알고리즘이 최선의 선택이 될 수 있다. 그럼 점근적 표기법을 알아보자.

$\Theta$-Notation

최악의 경우 삽입 정렬의 실행 시간은 $T(n) = \Theta(n^2)$으로 표현하였다. 그럼 $\Theta$는 무슨 의미를 가질까? 주어진 함수 $g(n)$에 대해 $\Theta(g(n))$은 다음과 같은 의미를 가진다.

$\Theta(g(n))$ = {$f(n)$ : there exist positive constants $c_1, c_2,$ and $n_0$ such that $0 \le c_1g(n) \le f(n) \le c_2g(n)$ for all $n \ge n_0$}.

함수 $f(n)$이 $\Theta(g(n))$에 속한다는 것을 $f(n) = \Theta(g(n))$으로 표기할 수 있다. $\Theta(g(n))$에 속한다는 의미는 양인 상수 $c_1, c_2$에 대해 $c_1 g(n)$과 $c_2 g(n)$ 사이에 $f(n)$이 존재한다는 의미로, "sandwiched"라는 뜻이다. 엄밀하게 따지면 $f(n) \in \Theta(g(n))$으로 표기해야하지만 여기서는 $=$기호를 사용하도록 하자.

Example 1)

$T(n)=\frac{n(n-1)}{2}$라면 $T(n) \in \Theta(n^2)$라 할 수 있는가?

Solution

$n_0 = 1$이라 두자. 이 때 $0 \le c_1 n^2 \le T(n) \le c_2 n^2$을 만족하는 $c_1$과 $c_2$가 존재하면 된다.

$n\ge1$일 때, 가능한 $c_1, c_2$가 존재할 수 있기 때문에 $\Theta(n^2)$에 속한다고 할 수 있다.

O-Notation

$f(n) = O(g(n))$ 혹은 $f(n) \in O(g(n))$의 의미는 다음과 같다.

$O(g(n))$ = {$f(n)$ : there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le cg(n)$ for all $n \ge n_0$}.

O-notation은 상한선(upper bound)를 의미한다. 즉 최악의 경우 총 계산 시간이 어떻게 되는지를 알고 싶을 때 사용한다.

Example 1)

$T(n) = \frac{n(n-1)}{2}$ 일 때, $T(n) \in O(n^2)$인가?

Solution

$n \neq 0$일 때, $c=1/2$이면 $-1 \le 0$이므로 등호가 성립한다. 즉, $O(n^2)$에 속한다.

$\Omega(n^2)$-Notation

$\Theta(g(n))$ = {$f(n)$ : there exist positive constants $c$ and $n_0$ such that $0 \le cg(n) \le f(n)$ for all $n \ge n_0$}.

O-notation와 비슷하다. 다만 부호의 차이로 $\Omega$-notation은 하한선을 의미한다. 즉, 최선의 경우의 총 실행시간을 의미한다.

Example 1)

$T(n) = \frac{n(n-1)}{2} \in \Omega(n^2)$ ?

Solution

$c=1/4, n_0=2$이면 위 등호가 만족하므로 $T(n) \in \Omega(n^2)$이다.

결론

알고리즘의 효율성을 따져보기 위해 최악의 경우를 고려했다. 최악의 경우의 알고리즘의 총 계산시간을 비교하기 위해 우리는 Order of Growth처럼 $n$의 크기가(문제의 크기가) 충분히 큰 경우를 고려해 점근적 표기법으로 나타내는 방법을 배웠다. 병합 정렬의 계산 시간을 $\Theta$-notation으로 표현할 때처럼 $T(n)$이 점화식(Recurrences)로 되어 있는 경우에 어떻게 구하는지를 다음시간에 알아보자.