Big-O(빅 오) 표기법: 점근 표기법

1. 개요

Big-O 표기법은 보통 시간 복잡도 혹은 공간 복잡도를 나타내기 위해 주로 사용한다.

많은 알고리즘들의 성능을 평가할 때 많이 등장하게 될 것인데, 그 중 한 예시로 정렬에서 다음과 같은 것을 접해보았을 것이다.

ex) 정렬 알고리즘의 시간복잡도

병합 정렬, 힙 정렬: $O(n\log{n})$

삽입 정렬, 선택 정렬: $O(n^2)$

위 표기의 의미는 간단하게 다음과 같이 이해하기 바란다.

/*

n개의 원소를 정렬할 때,

병합 정렬과 힙 정렬을 하는 데에 걸리는 시간은 $n\log{n}$에 비례하여 증가하고,

삽입 정렬과 선택 정렬을 하는 데에 걸리는 시간은 $n^2$에 비례하여 증가한다.

*/

2. 복잡도의 순위 & 낮은 복잡도의 중요성

보통 점근 표기법을 할 때는 앞에 붙은 계수는 무시하며, 높은 복잡도만 표기한다.

예를 들어서, 길이 n일 때 소요시간이 $5n^2+3n+2$로 증가하는 함수가 있다고 가정하자.

이 때, n이 커질수록 뒤의 두 항은 맨 앞의 $5n^2$에 비해 미미한 수치가 되기 때문에 무시해줄 수 있다.

또, $n^2$앞에 붙은 계수는 증가양상을 파악하는 데에 크게 영향을 주지 않으므로 무시해주어, 최종적으로 $O(n^2)$와 같이 표기한다.

복잡도는 보통 다음과 같은 순위를 가진다. 순위가 낮을수록 더 효율적인 알고리즘을 뜻한다고 생각할 수 있다.

$O(1)$ (상수)

$<O(\log{n})$ (로그)

$<O(n)$ (선형)

$<O(n\log{n})$ (선형로그)

$<O(n^2)<O(n^3)<...$ (다항식)

$<O(2^n)<O(3^n)<...$ (지수)

$<O(n!)$ (팩토리얼)

낮은 복잡도를 가지는 알고리즘은 n이 커질수록 유리해진다.

일상 생활에서 사용할 정도의 작은 규모라면 복잡도가 높아도 상관없겠지만, 요즘은 데이터가 수없이 생산되고 있으며 큰 데이터를 다룰 수 있을수록 유리하다.

만일 시간복잡도를 $O(n^2)$에서 $O(n\log{n})$으로 바꾸는 알고리즘을 찾아냈다고 하자.

n이 100만 정도의 크기만 되어도, 둘은 약 10만 배 정도의 차이를 보이게 된다.

더 나은 알고리즘으로는 1분이 걸릴 것을 10만 분을 들여서 사용할 사람은 어디에도 없을 것이라 생각한다.

3. 점근 표기법의 엄밀한 정의

Big-O 표기법의 엄밀한 정의는 다음과 같다.

$O(g(n))$ = $\lbrace f(n)$ : 모든 $n \ge n_0$에 대해 $0 \le f(n) \le cg(n)$인 양의 상수 $c, n_0$가 존재한다.$\rbrace$

처음 보는 사람은 어리둥절할 수 있겠지만, 간단히 설명하면 일정 크기 이상의 수에 대해서, g(n)을 상수배한 함수로 f(n)의 상한선을 그을 수 있다는 뜻이다.

간단한 예시로 아까 본 $5n^2+3n+2$을 살펴보자.

1 이상의 정수들에 대해서

$5n^2+3n+2 < 5n^2+3n^2+2n^2 = 10n^2 (n \ge 1)$

로 상한선을 그을 수 있다. 즉, $5n^2+3n+2$은 무슨 일이 있어도 n이 1 이상일 때 $10n^2$을 넘지 않는다.

이 때 $5n^2+3n+2$은 $O(n^2)$이라고 할 수 있다. (조금 더 정확한 표현으로는 $O(n^2)$의 원소이다)

4. 그 외 다양한 표기법들

상한 점근과 마찬가지로 하한 점근, 상/하한 점근 두 가지가 더 존재한다.

하한 점근은 $\Omega (g(n))$(Big-Omega)을, 상/하한 점근은 $\Theta (g(n))$(Big-Theta)를 사용한다.

상/하한을 동시에 만족해야 하므로 가장 strick한 점근이 Big-Theta라고 할 수 있는데, 시간 복잡도 측면에서는 best case에서 더 빠를 가능성이 있기 때문에, Big-Theta보다는 Big-O가 더 나을 것이다.

그 외 소문자를 사용하는 $o(g(n)), \; \omega(g(n))$ 또한 존재하는데 대문자에 비한다면 큰 중요성은 없으니 생략한다.