빅 오 표기법

빅 오 표기법은 알고리즘의 성능을 대략적으로 분석하기 위해 사용한다. 입력 크기 $n$이 무한히 커질 때 실행 시간이 어떻게 변화하는지를 평가하는 것이 주요 목적이다. 이 표기법은 정확한 연산 횟수보다는 데이터 증가에 따른 성능 변화의 추이를 파악하는 데 중점을 둔다.

빅 오 표기법은 함수의 점근적 상한을 제공한다. 즉, 어떤 함수 $f(n)$이 $O(g(n))$이라는 것은 충분히 큰 $n$에 대해 $f(n)$이 $g(n)$의 상수 배를 넘지 않는다는 의미이다. 이를 통해 알고리즘의 최악의 경우 성능을 보장할 수 있다.

빅 오 표기법은 독일 수학자 파울 바흐만이 1892년 정수론에 관한 저서에서 처음 사용하였다. 문자 'O'는 근삿값의 순서를 의미하는 독일어 'Ordnung'에서 따왔다. 이후 에드문트 란다우가 이 표기법을 널리 보급하여 '바흐만-란다우 표기법'이라고도 부른다.

컴퓨터 과학에서는 도널드 커누스가 1960년대 후반 《The Art of Computer Programming》에서 빅 오 표기법을 알고리즘 분석에 도입하면서 널리 사용되기 시작하였다. 커누스는 또한 빅 오메가(Ω)와 빅 세타(Θ) 표기법을 함께 소개하여 점근 표기법 체계를 완성하였다.

빅 오 표기법의 수학적 정의는 다음과 같다. $f(n)$과 $g(n)$이 양의 정수 $n$에 대해 정의된 함수라고 할 때, $f(n) = O(g(n))$이라는 것은 다음 조건을 만족하는 양의 상수 $c$와 $n_0$가 존재함을 의미한다.

$0 \leq f(n) \leq c \cdot g(n) \quad \text{for all } n \geq n_0$

즉, 충분히 큰 $n$에 대해 $f(n)$이 $g(n)$의 상수 배 이하로 제한된다는 뜻이다. 이 정의는 알고리즘의 최악의 경우 실행 시간이 $g(n)$의 증가율을 넘지 않음을 보장한다.

예를 들어, $f(n) = 3n^2 + 2n + 1$일 때 $f(n) = O(n^2)$이다. $c=4$, $n_0=1$로 잡으면 $3n^2 + 2n + 1 \leq 4n^2$이 성립하기 때문이다.

알고리즘 분석에서 자주 등장하는 시간 복잡도 클래스는 다음과 같다.

이 외에도 $O(n^3)$(삼차 시간), $O(\sqrt{n})$ 등 다양한 복잡도가 존재한다.

빅 오 표기법 외에도 알고리즘의 성능을 다양한 관점에서 분석하기 위한 점근 표기법이 존재한다.

• 빅 오메가(Ω) 표기법: 알고리즘 성능의 하한을 나타낸다. $f(n) = \Omega(g(n))$은 충분히 큰 $n$에 대해 $f(n)$이 $g(n)$의 상수 배 이상임을 의미한다. 즉, 최선의 경우 성능을 표현할 때 사용한다.
• 빅 세타(Θ) 표기법: 상한과 하한을 동시에 나타낸다. $f(n) = \Theta(g(n))$은 $f(n) = O(g(n))$이면서 $f(n) = \Omega(g(n))$일 때 성립하며, 알고리즘의 평균적인 성장률을 정확히 기술한다.
• 리틀 오(o) 표기법: $f(n) = o(g(n))$은 $f(n)$이 $g(n)$보다 느리게 증가함을 의미한다. 즉, $\lim_{n \to \infty} f(n)/g(n) = 0$이다.
• 리틀 오메가(ω) 표기법: $f(n) = \omega(g(n))$은 $f(n)$이 $g(n)$보다 빠르게 증가함을 의미한다. 즉, $\lim_{n \to \infty} f(n)/g(n) = \infty$이다.

이러한 표기법들은 알고리즘의 성능을 다각도로 분석하고 비교하는 데 유용하다.

빅 오 표기법은 컴퓨터 과학에서 알고리즘의 효율성을 비교하는 표준 도구로 자리 잡았다. 특히 대규모 데이터를 다루는 시스템에서 알고리즘 선택의 기준이 된다. 또한 수학에서는 해석적 수론에서 수론적 함수의 증가 경계를 표현하거나, 미적분학에서 멱급수의 오차를 제한하는 데 사용된다.

그러나 빅 오 표기법에는 몇 가지 한계가 있다. 첫째, 상수 계수를 무시하므로 실제 실행 시간이 같은 복잡도 클래스 내에서 크게 다를 수 있다. 둘째, 최악의 경우만 고려하므로 평균적인 성능이나 실제 입력 분포를 반영하지 못할 수 있다. 셋째, 입력 크기가 작을 때는 점근적 분석이 실제 성능과 맞지 않을 수 있다. 따라서 빅 오 표기법은 알고리즘의 이론적 분석 도구로 사용되며, 실제 구현에서는 추가적인 벤치마킹이 필요하다.