점근 표기법 완벽 가이드 - O(), o(), Ω(), ω(), Θ()의 정의와 차이

점근 표기법(Asymptotic Notations)이란?

점근 표기법은 알고리즘의 시간 복잡도와 공간 복잡도를 점근적 분석(asymptotic analysis)으로 나타내기 위해 사용되는 수학적 도구입니다. 입력 크기 n이 무한히 커질 때 알고리즘의 성능이 어떻게 변화하는지를 간결하게 표현할 수 있어, 알고리즘의 효율성을 비교하고 평가하는 데 필수적으로 활용됩니다.

대표적인 점근 표기법은 다음과 같습니다.

• 빅오(Big-O) 표기법 — O()
• 리틀 오(little-o) 표기법 — o()
• 빅 오메가(Big-Omega) 표기법 — Ω()
• 리틀 오메가(little-omega) 표기법 — ω()
• 빅 세타(Big-Theta) 표기법 — Θ()

빅오(Big-O) 표기법

빅오(O) 표기법은 함수 f(n)에 대한 상수 배수 범위 내의 상한(upper bound)을 나타냅니다.

수학적으로는 다음과 같이 정의됩니다.

f(n) = O(g(n)) ⇔ 상수 c > 0과 n₀가 존재하여, 모든 n ≥ n₀에 대해 0 ≤ f(n) ≤ c·g(n)

예를 들어, 어떤 알고리즘의 실행 시간이 O(n²)이라면, 입력 크기가 충분히 커졌을 때 그 실행 시간은 n²의 상수 배를 넘지 않는다는 의미입니다. 따라서 빅오 표기법은 주로 최악의 경우(worst case) 성능을 표현하는 데 사용됩니다.

리틀 오(little-o) 표기법

빅오, 빅 오메가, 빅 세타 외에도 몇 가지 보조 표기법이 있으며, 리틀 오(o) 표기법이 그 대표적인 예입니다.

리틀 오 표기법은 타이트(tight)하지 않은, 즉 느슨한(loose) 상한을 나타낼 때 사용합니다. 빅오와 달리 상한선에 '도달할 수 없다'는 조건이 포함되는 것이 핵심 차이입니다.

f(n) = o(g(n)) ⇔ 임의의 상수 c > 0에 대해 n₀가 존재하여, 모든 n ≥ n₀에 대해 0 ≤ f(n) < c·g(n)

예를 들어 f(n) = n일 때, f(n) = o(n²)은 성립하지만 f(n) = o(n)은 성립하지 않습니다. 즉, 리틀 오는 성장률이 엄격하게 더 느린 경우에만 사용됩니다.

빅 오메가(Big-Omega) 표기법

빅 오메가(Ω) 표기법은 함수 f(n)에 대한 상수 배수 범위 내의 하한(lower bound)을 나타냅니다.

f(n) = Ω(g(n)) ⇔ 상수 c > 0과 n₀가 존재하여, 모든 n ≥ n₀에 대해 0 ≤ c·g(n) ≤ f(n)

즉, 알고리즘의 실행 시간이 아무리 좋은 상황에서도 g(n)보다 빠르게 줄어들 수 없음을 의미하며, 주로 최선의 경우(best case) 성능을 표현하는 데 활용됩니다.

리틀 오메가(little-omega) 표기법

리틀 오메가(ω) 표기법은 리틀 오와 마찬가지로 보조적으로 사용되는 점근 표기법입니다.

리틀 오메가는 f(n)에 대한 느슨한(loose) 하한을 나타냅니다. 하한선에 도달할 수 없으며, 성장률이 엄격하게 더 빠른 경우에만 성립합니다.

f(n) = ω(g(n)) ⇔ 임의의 상수 c > 0에 대해 n₀가 존재하여, 모든 n ≥ n₀에 대해 0 ≤ c·g(n) < f(n)

예를 들어 f(n) = n²일 때, f(n) = ω(n)은 성립하지만 f(n) = ω(n²)은 성립하지 않습니다.

빅 세타(Big-Theta) 표기법

빅 세타(Θ) 표기법은 함수 f(n)에 대한 상수 배수 범위 내의 상한과 하한을 동시에 나타냅니다. 즉, 알고리즘의 성장률을 가장 정확하게 묘사할 수 있는 표기법입니다.

f(n) = Θ(g(n)) ⇔ 상수 c₁, c₂ > 0과 n₀가 존재하여, 모든 n ≥ n₀에 대해 c₁·g(n) ≤ f(n) ≤ c₂·g(n)

따라서 f(n) = Θ(g(n))이 성립하면, 동시에 f(n) = O(g(n))과 f(n) = Ω(g(n))이 모두 참임을 알 수 있습니다.

정리: 다섯 가지 표기법 비교

점근 표기법을 올바르게 이해하면 알고리즘의 성능을 입력 크기에 따라 체계적으로 분석할 수 있으며, 문제 상황에 맞는 최적의 알고리즘을 선택하는 데 큰 도움이 됩니다.