0x02. 함수의 증가와 점근적 표기법

왜 함수의 증가율이 중요한가?

알고리즘의 효율성을 비교할 때 가장 핵심적인 지표는 수행 시간(Running Time)의 증가율(Order of Growth) 이다. 입력 크기 $n$이 커질수록 수행 시간이 $n$에 비례하는지, $n^2$에 비례하는지, 아니면 $\log n$에 비례하는지에 따라 알고리즘의 실용성이 완전히 달라진다.

이때 점근적 효율성(Asymptotic Efficiency) 이라는 개념을 사용한다. 입력 크기가 한없이 커질 때 수행 시간이 어떻게 증가하는지를 분석하는 것이다. 작은 입력에서는 비효율적인 알고리즘이 더 빠를 수도 있지만, 입력이 충분히 커지면 점근적으로 더 효율적인 알고리즘이 반드시 승리한다.

점근적 분석에서는 낮은 차수의 항(Low-order Terms) 과 상수 인자(Constant Factors) 를 무시한다. $3n^2 + 5n + 7$ 같은 수행 시간은 결국 $n^2$의 증가율을 따르기 때문이다. 핵심만 남기고 나머지는 추상화하는 것이 점근적 표기법의 철학이다.

점근적 표기법 (Asymptotic Notations)

점근적 표기법은 알고리즘의 수행 시간을 간결하게 표현하는 수학적 도구다. 크게 다섯 가지가 있으며, 가장 자주 사용되는 세 가지는 O, $\Omega$, $\Theta$ 표기법이다.

O-notation: 상한 (Upper Bound)

Big-O 표기법은 함수의 점근적 상한을 나타낸다. $f(n) = O(g(n))$이라 함은, 충분히 큰 $n$에 대해 $f(n)$이 $c \cdot g(n)$을 넘지 않는 양의 상수 $c$와 $n_0$가 존재한다는 뜻이다.

쉽게 말해 "최악의 경우에도 이 정도보다 나쁘지는 않다"라는 보장이다. 실무에서 가장 많이 사용되는 표기법으로, 알고리즘의 최악 성능의 상한선을 제시한다.

Ω-notation: 하한 (Lower Bound)

Big-Omega 표기법은 함수의 점근적 하한을 나타낸다. $f(n) = \Omega(g(n))$이라 함은, 충분히 큰 $n$에 대해 $f(n)$이 $c \cdot g(n)$ 이상인 양의 상수 $c$와 $n_0$가 존재한다는 뜻이다.

"최소한 이 정도의 시간은 걸린다"라는 의미로, 알고리즘의 최선 성능의 하한선을 제시한다.

Θ-notation: 정확한 한계 (Tight Bound)

Big-Theta 표기법은 함수의 점근적 정확한 한계를 나타낸다. $f(n) = \Theta(g(n))$이라 함은, $f(n) = O(g(n))$이면서 동시에 $f(n) = \Omega(g(n))$인 경우다.

상한과 하한이 같은 차수이므로 "정확히 이 정도 수준으로 증가한다"라는 가장 정밀한 표현이다. 세 표기법 중 가장 많은 정보를 담고 있다.

정리와 규칙

$f(n) = \Theta(g(n))$이 성립할 필요충분조건은 $f(n) = O(g(n))$이고 $f(n) = \Omega(g(n))$인 것이다. 이 정리를 활용하면, 상한과 하한을 각각 보인 뒤 $\Theta$를 결론짓는 방식으로 증명할 수 있다.

o-notation: 엄격한 상한

Little-o 표기법은 Big-O보다 더 엄격한 상한을 나타낸다. $f(n) = o(g(n))$이라 함은, 모든 양의 상수 $c$에 대해 f(n) < c \cdot g(n)을 만족하는 $n_0$가 존재한다는 뜻이다. 즉 $f(n)$이 $g(n)$보다 확실히 느리게 증가한다.

Big-O에서는 "같거나 느리다"(≤)이고, Little-o에서는 "확실히 느리다"(<)이다. 예를 들어 $n = o(n^2)$은 참이지만, $n^2 = o(n^2)$은 거짓이다.

ω-notation: 엄격한 하한

Little-omega 표기법은 Big-Omega보다 더 엄격한 하한을 나타낸다. Little-o와 대칭적인 관계로, $f(n)$이 $g(n)$보다 확실히 빠르게 증가함을 의미한다.

표기법 사용 예시

시간 복잡도(Time Complexity) 문제를 풀 때는 반드시 적절한 표기법을 명시해야 한다. 상한만 말할 때는 O를, 하한만 말할 때는 $\Omega$를, 정확한 차수를 말할 때는 $\Theta$를 사용한다.

명제 (Proposition)

점근적 표기법 사이의 관계를 보여주는 주요 명제들이다. 이 관계들은 표기법 간의 포함 관계와 대칭성을 이해하는 데 도움이 된다.

알고리즘의 최적성 (Optimality)

모든 문제에는 내재적 복잡도(Inherent Complexity) 가 있다. 즉, 그 문제를 풀기 위해 반드시 필요한 최소한의 연산량이 존재한다. 이를 문제의 하한(Lower Bound of Problem) 이라 한다.

어떤 알고리즘의 최악 시간 복잡도(Worst-case Time Complexity) 가 해당 문제의 하한과 일치하면, 그 알고리즘을 최적(Optimal) 이라 한다.

여기서 주의할 점이 있다. "최적"이란 "현재 알려진 것 중 최고(the best known)"가 아니라 "이론적으로 가능한 최고(the best possible)"를 의미한다. 아무리 기발한 알고리즘을 고안하더라도 문제의 하한보다 더 빠른 알고리즘은 존재할 수 없다.

예시

점근적 성능 비교

입력 크기 $n$이 커질수록, 알고리즘의 증가율 차이는 극적으로 벌어진다. $O(n \log n)$ 알고리즘과 $O(n^2)$ 알고리즘은 작은 입력에서는 큰 차이가 없지만, 입력이 수만, 수십만 단위로 커지면 성능 차이가 수십~수백 배로 벌어진다.

함수 성장의 계층 구조 (Hierarchy of Orders)

함수의 증가율에는 명확한 계층이 있다. 느린 것부터 빠른 것 순으로 나열하면 다음과 같다.

$1 < \log n < \sqrt{n} < n < n \log n < n^2 < n^3 < 2^n < n!$

이 계층 구조를 외워두면, 주어진 알고리즘의 효율성을 직관적으로 비교할 수 있다. 다항 시간(Polynomial Time) 안에 해결 가능한 문제와, 지수 시간(Exponential Time)이 필요한 문제 사이에는 넘을 수 없는 벽이 있다.

연습문제

1. Big-O 정의 적용

$O(g(n))$ = { $f(n)$ : 양의 상수 $c$와 $n_0 > 0$이 존재하여, 모든 $n ≥ n_0$에 대해 $0 ≤ f(n) ≤ c \cdot g(n)$ }

문제: $5n^2 = O(n^3)$에서, 조건을 만족하는 $n_0$과 $c$의 값을 구하라.

풀이: $(n_0, c)$: $(1, 5)$ 또는 $(5, 1)$

$n_0 = 1, c = 5$인 경우, $n ≥ 1$에서 $5n^2 ≤ 5n^3$이 항상 성립한다. $n_0 = 5, c = 1$인 경우, $n ≥ 5$에서 $5n^2 ≤ n^3$이 성립한다.

2. 참/거짓 판별

1) $5n^2 = O(n^3)$ : T

2) $f(n) = O(g(n))$과 $O(g(n)) = f(n)$이 같은 의미인가? : F

점근적 표기법에서 등호(=)는 일반적인 등호가 아니라 "~에 속한다"의 의미다. $n^2 = O(n^3)$이 참이라고 해서 $n^3 = O(n^2)$이 참이 되지는 않는다. 방향이 다르다.

3) $n^2 + O(n) = O(n^2)$ : T

4) $\frac{1}{2}n^2 = \Theta(n^2)$ : T

5) $\frac{1}{2}n^2 = o(n^2)$ : F

$\frac{1}{2}n^2$과 $n^2$은 같은 차수이므로, 엄격한 상한인 $o$-notation은 성립하지 않는다. $\Theta(n^2)$은 맞지만 $o(n^2)$은 아니다.

6) $f(n) + g(n) = \Theta(\min(f(n), g(n)))$ : F

두 함수의 합은 더 큰 쪽에 의해 지배되므로, $\Theta(\max(f(n), g(n)))$이 맞다.

7) $f(n) = O(g(n))$이면 $\lg(f(n)) = O(\lg(g(n)))$인가? : T

8) $f(n) = O(g(n))$이면 $2^\{f(n)\} = O(2^\{g(n)\})$인가? : F

반례: $2n = O(n)$이지만, $2^\{2n\} = 4^n$이고 $2^n$과 비교하면 $4^n \neq O(2^n)$이다. 지수 함수에서는 상수 배의 차이가 지수적 차이로 증폭된다.

9) $f(n) = O((f(n))^2)$인가? : F

반례: $f(n) = 1/n$이면 $f(n)^2 = 1/n^2$이다. $1/n$은 $1/n^2$보다 빠르게 증가하므로 $1/n = O(1/n^2)$이 성립하지 않는다.

10) $f(n) = O(g(n))$이면 $g(n) = \Omega(f(n))$인가? : T

O와 $\Omega$는 대칭 관계다. $f$가 $g$ 이하라면, $g$는 $f$ 이상이다.

11) $f(n) = \Theta(f(n/2))$인가? : F

반례: $f(n) = 2^\{2n\}$이면 $f(n/2) = 2^n$이다. $2^\{2n\} = 4^n$이므로 $4^n \neq \Theta(2^n)$이다.

12) $f(n) + o(f(n)) = \Theta(f(n))$ : T

$o(f(n))$은 $f(n)$보다 확실히 느리게 증가하므로, $f(n)$에 더해도 전체 차수를 바꾸지 못한다.

3. 점근적 관계

$\lg n$과 $\log_8 n$의 관계에서 성립하는 것을 모두 고르라.

1. $\lg n = O(\log_8 n)$
2. $\lg n = \Omega(\log_8 n)$
3. $\lg n = \Theta(\log_8 n)$

답: 모두 참

로그의 밑 변환 공식에 의해 $\lg n = \log_8 n \times \log_2 8 = 3 \log_8 n$이다. 즉 두 함수는 상수 배 차이만 나므로, O, $\Omega$, $\Theta$ 관계가 모두 성립한다. 점근적 표기법에서 로그의 밑은 무관하다.

4. 2²ⁿ = O(2ⁿ)인가?

아니다.

$2^\{2n\} = 2^n \cdot 2^n$이므로, $2^n \cdot 2^n ≤ c \cdot 2^n$을 만족하려면 $2^n ≤ c$여야 한다. 하지만 $n$이 커질수록 $2^n$은 한없이 커지므로, 이를 만족하는 상수 $c$와 $n_0$는 존재하지 않는다.

HGU 전산전자공학부 용환기 교수님의 23-1 알고리듬 분석 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.