[알고리즘] 알고리즘의 차수와 복잡도 함수

복잡도함수의 분류와 차수

복잡도 분류 (Complexity categories)

[ 복잡도 분석 시 핵심 원칙 ]
• 낮은 차수의 항은 무시할 수 있다
• 예: $0.1n^2 + n + 100$에서 $n$과 상수항은 $n^2$에 비해 무시 가능
→ 그래서 이 함수는 Θ(n²)로 분류됨

[ n차 시간 알고리즘과 순수 n차 함수 ]
• 순수 n차 함수: 다른 차수항 없이 해당 차수항만 포함
• n차 시간 알고리즘: 다른 차수항이 있어 순수 n차 함수는 아니지만 n차 시간 알고리즘 으로 분류 가능

(n)	$0.1n^2$	$0.1n^2 + n + 100$
10	10	120
20	40	160
50	250	400
100	1,000	1,200
1,000	100,000	101,100

→ 입력 크기 n이 커질수록 나머지 항의 영향은 작아짐
→ 결국 두 함수는 동일한 차수로 분류 가능 (Θ(n²))

Θ 표기법과 차수 분류

• 어떤 함수 $g(n)$이 Θ(n²)에 속하면,
→ “이차 시간 함수”, 또는 “Θ(n²) 알고리즘”이라고 말함

• 예시 알고리즘:
교환 정렬 (exchange sort)
$T(n) = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} \Rightarrow Θ(n^2)$

대표적인 복잡도 분류 계층

• Θ(log n) < Θ(n) < Θ(n log n) < Θ(n²) < Θ(n³) < Θ(2ⁿ)

참고
• Θ(2ⁿ): 컴퓨터가 다루기 어려운 수준
• 일반적으로 왼쪽으로 갈수록 더 효율적인 알고리즘

점근표기법(Asymptotic Notation)

알고리즘이 입력 크기 n에 따라 어떻게 성능이 변하는지를 표현하는 방법
함수의 “성장 속도”를 기준으로 알고리즘의 효율을 비교할 수 있게 해줌
• Big-O 표기법 (O)
• Omega 표기법 (Ω)
• Theta 표기법 (Θ)
• 소문자 o 표기법 (little-o)

Big-O 표기법 (O)

[ 정의 ]

함수 $g(n) \in O(f(n))$란,
양의 실수 상수 $c$와 정수 $N \geq 0$가 존재하여
모든 $n \geq N$에 대해 $g(n) \leq c \cdot f(n)$

• 즉, $g(n)$은 결국 $c \cdot f(n)$보다 느리지 않다
• 처음에는 $g(n)$이 커 보일 수 있지만, 충분히 큰 n부터는 항상 $c \cdot f(n)$ 아래에 있게 됨

📌 Big-O는 최악의 경우 시간 복잡도를 표현하며, 상한(upper bound)을 의미

[ 예제들 ]

$g(n) = n^2 + 10n$은 $O(n^2)$
• 왜냐하면 $n \geq 1$일 때 $n^2 + 10n \leq 11n^2$
• ⇒ $c = 11, N = 1$

$5n^2 \in O(n^2)$
• $5n^2 \leq 5n^2$, ⇒ $c = 5, N = 0$

교환 정렬 (Exchange Sort)
• $T(n) = \frac{n(n-1)}{2} \leq \frac{n^2}{2} \Rightarrow T(n) \in O(n^2)$
• ⇒ $c = 1/2$, $N = 0$

$n^2 \in O(n^2 + 10n)$
• 가능함! $n^2 \leq 1 \cdot (n^2 + 10n)$ (단순한 함수만 오는 게 아니라 복합 함수도 가능)
• ⇒ $c = 1$, $N = 0$

📈 시각적 설명:
초기에는 $g(n)$이 $c \cdot f(n)$보다 클 수 있지만,
일정 시점 이후에는 항상 작아지며 계속 그 아래에 머무름

Omega 표기법 (Ω)

[ 정의 ]

함수 $g(n) \in \Omega(f(n))$란,
양의 상수 $c$, 정수 $N \geq 0$가 존재해서
모든 $n \geq N$에 대해 $g(n) \geq c \cdot f(n)$

📌 즉, $g(n)$은 결국 $c \cdot f(n)$보다 빠르지 않다, 혹은 그 이상이다
⇒ 최선의 경우 시간 복잡도 표현에 사용됨 (하한, lower bound)

예제

$n^2 + 10n \in \Omega(n^2)$
• $n^2 + 10n \geq n^2$
• ⇒ $c = 1, N = 0$

$5n^2 \in \Omega(n^2)$
• ⇒ $5n^2 \geq 1 \cdot n^2$
• ⇒ $c = 1, N = 0$

교환 정렬
$T(n) = \frac{n(n-1)}{2} \geq \frac{1}{4}n^2 \quad \text{(for } n \geq 2 \text{)}$
• $c = 1/4$, $N = 2$
• $T(n) \in \Omega(n^2)$

$n^3 \in \Omega(n^2)$
• $n \geq 1$일 때, $n^3 \geq 1 \cdot n^2$
• 당연히 포함됨 (차수가 더 크므로)

📈 시각적 설명:
처음엔 작을 수 있지만, 결국 $g(n)$이 $c \cdot f(n)$보다 커져서 계속 위에 머물게 됨

Theta 표기법 (Θ)

정의

함수 $g(n) \in \Theta(f(n))$란,
상수 $c_1, c_2 > 0$, 정수 $N \geq 0$가 존재하여
모든 $n \geq N$에 대해 $c_1 f(n) \leq g(n) \leq c_2 f(n)$

• 즉, $g(n)$이 $f(n)$과 성장률이 정확히 같은 수준이라는 뜻
• O와 Ω를 동시에 만족하면 Θ에 속함
$\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$

📌 정확한 차수의 복잡도 표현, 즉 평균적 수행 시간에 사용

예시

교환 정렬 알고리즘
• $T(n) = \frac{n(n-1)}{2} \in O(n^2)$, $\Omega(n^2)$
• $T(n) \in \mathcal{O}(n^2) \cap \Omega(n^2) = \Theta(n^2)$
• $4n^2, 6n^2 + 9, 5n^2 + 2n$ 등도 $\Theta(n^2)$에 속함

소문자 o 표기법 (little-o)

[ 정의 ]

주어진 복잡도 함수 $f(n)$에 대해,
$o(f(n))$는 다음 조건을 만족하는 모든 복잡도 함수 $g(n)$의 집합
• 모든 양의 실수 상수 $c$에 대해, 음이 아닌 정수 $N$이 존재하여,
모든 $n \geq N$에 대해, $g(n) \leq c \cdot f(n)$

• Big-O: 특정 상수 ( c )가 존재하면 된다
• small-o는 모든 양의 상수 ( c )에 대해 조건이 성립해야 한다

[ 예시 ]

만약 $g(n) \in o(f(n)$라면,
$g(n) \leq 0.00001 \cdot f(n)$ 같은 식도 어떤 $N$이후에 성립해야 함
👉 결론:
• $g(n)$이 $f(n)$에 비해 의미 없을 정도로 작아진다면 $g(n) \in o(f(n))$이다
• 분석 관점에서 보면, 이런 $g(n)$은 $f(n)$보다 훨씬 더 효율적

예제 1: $n \in o(n^2)$ • 어떤 $c > 0$에 대해 $n \leq cn^2$이 성립해야 함
• 양변을 $cn$으로 나누면: $\frac{1}{c} \leq n$
• 따라서 $N \geq \frac{1}{c}$이면 조건 만족
• 예: $c = 0.00001$이면 $N \geq 100{,}000$ 필요
• 즉, $n \leq 0.00001n^2$

예제 2: $n \notin o(5n)$
• 귀납기초: $n \in o(5n)$라면
귀납단계:
→ 어떤 $c = \frac{1}{6}$, $N$에 대해 $n \leq \frac{5}{6}n$ → 이는 항상 거짓이므로 모순 발생
• 결론: $n \notin o(5n)$

[ 정리된 정리 (Theorem 1.2) ]

만약 $g(n) \in o(f(n))$이면, $g(n) \in O(f(n)) \setminus \Omega(f(n))$
• 즉, Big-O에는 포함되지만 Big-Omega에는 포함되지 않음
• $g(n) \in o(f(n))$ ⇒ 모든 양의 상수 $c$에 대해 $g(n) \leq c \cdot f(n)$
• 귀류법으로 $g(n) \in \Omega(f(n))$라고 가정하면, 어떤 $c > 0$, $N_1$이 존재해 $g(n) \geq c \cdot f(n)$
• 그런데 $g(n) \in o(f(n))$이므로 어떤 $N_2$에 대해 $g(n) \leq \frac{c}{2} \cdot f(n)$
• 두 식은 모순됨 ⇒ 따라서 $(n) \notin \Omega(f(n))$

예제 3: 특이한 함수 \(g(n) = \begin{cases} n \text{ if } n \text{ is even} \\ 1 \text{ if } n \text{ is odd} \end{cases}\)
• 이 함수는 $g(n) \in O(n) \setminus \Omega(n)$ 이지만, $g(n) \notin o(n)$
• 짝수일 때는 선형이지만,
• 홀수일 때는 상수 함수라서 점근적으로는 너무 들쭉날쭉함.

요약 표

표기	의미	성장률 비교	용도
O(f(n))	상한	느리거나 같다	최악 시간 복잡도
Ω(f(n))	하한	빠르거나 같다	최선 시간 복잡도
Θ(f(n))	정확한 차수	같음	평균 시간 복잡도
o(f(n))	진정한 상한	훨씬 느림	O보다 더 엄격한 상한