점근 표기법(Asymptotic Notation)이란?
점근 표기법은 알고리즘의 성능을 점근적 분석(asymptotic analysis) 관점에서 평가하기 위해 사용되는 수학적 도구입니다. 입력 크기(n)가 충분히 커질 때 알고리즘의 실행 시간이나 메모리 사용량이 어떻게 증가하는지를 간결하게 표현할 수 있습니다.
점근 표기법에는 일반적으로 다음 세 가지가 널리 사용됩니다.
- 빅오 표기법 (Big-O, O) — 최악의 경우를 기준으로 하는 상한(Upper Bound)
- 빅 오메가 표기법 (Big-Omega, Ω) — 최선의 경우를 기준으로 하는 하한(Lower Bound)
- 빅 세타 표기법 (Big-Theta, Θ) — 상한과 하한이 모두 만족될 때의 평균적인 증가율
빅오 표기법(Big-O Notation)의 정의
빅오 표기법은 함수 f(n)의 증가율에 대한 상한선을 상수 배수 범위 안에서 나타냅니다. 쉽게 말해, 입력이 커질수록 알고리즘의 실행 시간이 '기껏해야 이 정도 속도로 느려진다'는 것을 의미합니다.
수학적으로는 다음과 같이 정의합니다.
f(n) = O(g(n))이라고 쓸 수 있는 조건은, 양의 상수 c와 n₀가 존재하여 n₀ 이상의 모든 n에 대해 항상 다음 부등식이 성립하는 경우입니다.
0 ≤ f(n) ≤ c·g(n), 모든 n ≥ n₀
이를 집합의 형태로 표현하면 다음과 같습니다.
O(g(n)) = { f(n) : 양의 상수 c와 n₀가 존재하여, 모든 n ≥ n₀에 대해 0 ≤ f(n) ≤ c·g(n) }
즉, n₀라는 기준점을 지나기만 하면 f(n)의 그래프가 c·g(n)의 그래프 아래쪽에 머무른다면, f(n)은 O(g(n))에 속한다고 말할 수 있습니다.
직관적인 이해
예를 들어 어떤 알고리즘의 실제 실행 시간이 f(n) = 3n² + 5n + 7이라고 가정해 봅시다. n이 충분히 커지면 낮은 차수의 항(5n, 7)은 무시할 수 있으므로, 이 알고리즘의 시간 복잡도는 O(n²)로 표현합니다. 빅오 표기법은 이처럼 성장률을 지배하는 최고 차수 항에만 주목하고 상수 계수는 제거하여 알고리즘의 효율성을 단순명료하게 비교할 수 있게 해줍니다.
대표적인 시간 복잡도 순서
일반적으로 자주 등장하는 빅오 표기법을 효율이 좋은 순서부터 나열하면 다음과 같습니다.
- O(1) — 상수 시간
- O(log n) — 로그 시간
- O(n) — 선형 시간
- O(n log n) — 선형 로그 시간
- O(n²) — 이차 시간
- O(2ⁿ) — 지수 시간
빅오 표기법은 알고리즘의 최악의 경우(worst case) 성능을 보장하는 안전한 상한선을 제공하기 때문에, 알고리즘 설계와 성능 분석에서 가장 널리 활용되는 표기법입니다.