점근 표기법(Asymptotic Notations)이란?
점근 표기법은 알고리즘의 복잡도(complexity)를 점근적으로 분석하기 위해 사용되는 수학적 도구입니다. 입력 크기 n이 커질 때 알고리즘의 실행 시간이나 자원 사용량이 어떻게 증가하는지를 간결하게 표현할 수 있어, 알고리즘의 성능을 비교하고 평가하는 데 필수적인 개념입니다.
일반적으로 가장 널리 사용되는 점근 표기법에는 세 가지가 있습니다.
- 빅 오(Big-O, O) : 상한(Upper Bound) 표기
- 빅 오메가(Big-Omega, Ω) : 하한(Lower Bound) 표기
- 빅 세타(Big-Theta, Θ) : 상한과 하한을 동시에 나타내는 타이트 바운드(Tight Bound) 표기
이 글에서는 그중 빅 오메가(Ω) 표기법과 빅 세타(Θ) 표기법에 대해 자세히 살펴보겠습니다.
빅 오메가(Big-Omega, Ω) 표기법
빅 오메가(Ω) 표기법은 함수 f(n)에 대한 하한(lower bound)을 상수 배수 범위 내에서 나타냅니다. 쉽게 말해, 알고리즘이 아무리 좋은 상황에서도 적어도 이만큼의 시간은 걸린다는 것을 의미합니다. 따라서 주로 알고리즘의 최선(best case) 성능을 분석할 때 활용됩니다.
수학적 정의
양의 상수 c와 n₀가 존재하여, n₀보다 크거나 같은 모든 n에 대해 f(n)이 항상 c·g(n) 위에 있거나 같다면, 다음과 같이 표기합니다.
f(n) = Ω(g(n))
이를 집합의 형태로 나타내면 다음과 같습니다.
Ω(g(n)) = { f(n) : 양의 상수 c와 n₀가 존재하여, 모든 n ≥ n₀에 대해 0 ≤ c·g(n) ≤ f(n)을 만족 }
그래프로 보면, n₀ 지점을 기준으로 그 오른쪽 구간에서 f(n)의 곡선이 c·g(n) 곡선보다 항상 위쪽에 위치하는 것을 확인할 수 있습니다.
빅 세타(Big-Theta, Θ) 표기법
빅 세타(Θ) 표기법은 함수 f(n)에 대한 상한과 하한을 동시에 상수 배수 범위 내에서 나타냅니다. 즉, f(n)의 증가율이 g(n)과 정확히 같은 차수(order)임을 의미하며, 알고리즘의 평균적인 성장률을 가장 정확하게 표현할 수 있는 표기법입니다.
수학적 정의
양의 상수 c₁, c₂와 n₀가 존재하여, n₀보다 크거나 같은 모든 n에 대해 f(n)이 항상 c₁·g(n)과 c₂·g(n) 사이(경계값 포함)에 있다면, 다음과 같이 표기합니다.
f(n) = Θ(g(n))
이를 집합의 형태로 나타내면 다음과 같습니다.
Θ(g(n)) = { f(n) : 양의 상수 c₁, c₂와 n₀가 존재하여, 모든 n ≥ n₀에 대해 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n)을 만족 }
그래프로 보면, n₀ 지점 이후의 구간에서 f(n)의 곡선이 c₁·g(n)과 c₂·g(n) 두 곡선 사이에 끼워져 있는 것을 확인할 수 있습니다. 이는 f(n)이 g(n)과 동일한 증가 속도를 가진다는 것을 의미합니다.
정리
빅 오메가(Ω)는 알고리즘 성능의 하한을, 빅 세타(Θ)는 상한과 하한을 모두 포함하는 정확한 경계를 나타냅니다. 두 표기법을 함께 이해하면 빅 오(O) 표기법과 더불어 알고리즘의 시간 복잡도를 입체적으로 분석할 수 있습니다.