점근적 표기법(Asymptotic Notations)이란?
점근적 표기법은 알고리즘의 복잡도를 점근적 분석(asymptotic analysis)으로 나타내기 위해 사용되는 수학적 도구입니다. 입력 크기 n이 충분히 커질 때 알고리즘의 실행 시간이나 메모리 사용량이 어떤 속도로 증가하는지를 간결하게 표현할 수 있어, 서로 다른 알고리즘의 성능을 비교하고 평가하는 데 필수적입니다. 가장 널리 사용되는 표기법은 다음의 세 가지입니다.
빅오 표기법(Big-Oh Notation)
빅오(O) 표기법은 함수 f(n)의 상한(upper bound)을 상수 배수 범위 내에서 나타냅니다. 즉, 알고리즘의 실행 시간이 최악의 경우에도 기준 함수 g(n)보다 빠르게 증가하지 않음을 의미하며, 알고리즘의 최악 성능을 분석할 때 가장 많이 활용됩니다.
양의 상수 c와 n₀가 존재하여, n ≥ n₀인 모든 n에 대해 f(n)이 항상 c·g(n) 위쪽 경계선 또는 그 아래에 위치할 때, f(n) = O(g(n))이라고 씁니다.
수학적 정의: O(g(n)) = { f(n) : 양의 상수 c와 n₀가 존재하여, 모든 n ≥ n₀에 대해 0 ≤ f(n) ≤ c·g(n) }
빅오메가 표기법(Big-Omega Notation)
빅오메가(Ω) 표기법은 함수 f(n)의 하한(lower bound)을 상수 배수 범위 내에서 나타냅니다. 이는 알고리즘이 어떤 경우에도 기준 함수 g(n)보다 느리게 증가할 수밖에 없음을 의미하며, 주로 최선의 경우(best case) 성능을 분석할 때 사용됩니다.
양의 상수 c와 n₀가 존재하여, 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) }
빅세타 표기법(Big-Theta Notation)
빅세타(Θ) 표기법은 함수 f(n)의 상한과 하한을 동시에 나타내는, 세 가지 표기법 중 가장 엄격한 표기법입니다. 알고리즘의 실행 시간이 상수 배수 범위 내에서 g(n)과 동일한 증가율을 가진다는 것을 의미하므로, 알고리즘의 정확한 성능 특성을 기술할 때 유용합니다.
양의 상수 c₁, c₂와 n₀가 존재하여, 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) }
세 가지 표기법 한눈에 비교하기
- 빅오(O): 상한 표기 — "아무리 늦어도 이 이상은 아니다" → 최악의 경우 분석
- 빅오메가(Ω): 하한 표기 — "아무리 빨라도 이 이하일 수 없다" → 최선의 경우 분석
- 빅세타(Θ): 상·하한 동시 표기 — "정확히 이 증가율이다" → 평균 및 전체적인 성능 분석
이처럼 점근적 표기법은 상수 계수나 하드웨어 환경 등 세부 요소를 제거하고 알고리즘 고유의 효율성만을 본질적으로 비교할 수 있게 해주는 강력한 분석 도구입니다.