Big-Oh Notation (빅-오 표기법)

프로그램의 실행시간을 흔히 시간복잡도(time complexity)라고 말한다. 알고리즘의 분석에 있어서 이 시간복잡도를 입력 자료의 크기 $n$ 의 함수로 나타내는 것이 일반적이다. 예를 들어, 다음과 같은 파이썬 코드가 있다고 하자.

def find_max(input_data):
    maximum = input_data[0]
    for element in input_data:
        if element > maximum:
            maximum = element
    return maximum

위의 파이썬 코드는 리스트 형태로 주어지는 input_data 의 요소 중 그 값이 가장 큰 것을 반환하는 함수 find_max 를 나타낸다. 이때 이 코드의 실행시간은 중간에 있는 for-loop 에 가장 큰 영향을 받게 되리라는 것을 생각할 수 있다. input_data 가 $n$ 개의 요소를 포함하는 리스트라고 할 때 for-loop 는 $n$ 번 반복되게 되므로 결국 이 코드의 실행시간에 가장 큰 영향을 주는 것은 바로 input_data 의 크기인 $n$ 이라고 할 수 있다. 따라서 이 코드의 시간복잡도는 $n$ 에 비례한다고 말할 수 있는 것이다. 

그러나 이렇게 단순히 $n$ 에 비례한다고 말하는 것보다는 좀 더 수학적인 표현을 사용하는 것이 폼나 보일 것이고, 그래서 나온 것이 바로 "Big-Oh" 표기법 이라는 것이다. (앞으로는 "빅오"라는 표현을 쓰도록 하겠다.)

함수 $f(n)$ 과 $g(n)$ 의 자연수를 양의 실수로 대응시키는 함수라고 할 때, 다음을 만족시키는 양의 상수 $c>0$ 와 정수 $n_0 \ge 1$ 이 존재하면 "$ f(n)$ is $O(g(n))$" 혹은 "$f(n) \in O(g(n))$" 이라고 쓰고, "$f(n)$ is big-Oh of $g(n)$" 혹은 "$f(n)$ is order of $g(n)$"으로 읽는다. $$f(n) \le c g(n), \text{        for       } n \ge n_0$$

다음 그림을 보면 빅오 표기법을 좀 더 쉽게 이해할 수 있을 것이다.

예를 들어, 함수 $8n+5$ 의 경우 $(c, \; n_0)$ 를 $(9, \; 5)$ 혹은 $(13, \; 1)$ 등으로 나타낼 수 있으므로 $O(n)$ 이 된다. 따라서 위에서 봤던 find_max 알고리즘의 경우도 $O(n)$ 으로 나타낼 수 있다. 

그렇다면 $f(n)=5n^4 +3n^3 + 2n^2 +4n+1$ 과 같이 복잡한 함수를 빅오 표기법으로 나타내면 어떻게 될까? 이때는 $n$ 이 증가함에 따라 가장 빠른 속도로 증가하는 놈에게 관심을 집중시켜야 한다. 즉, $n$ 이 커질수록 $1 \le n \le n^2 \le n^3 \le n^4$ 이므로 $n^4$ 에 만 관심을 집중시키면 된다. 이렇게 하면  $$5n^4 + 3n^3 +2n^2 + 4n +1 \le (5+4+2+5+1)n^4 = 15n^4$$ 이므로 $c=15, \;\; n_0 =1$ 로 결정할 수 있고, 결국 주어진 함수 $f(n)$ 은 $O \left ( n^4 \right )$ 로 표기할 수 있다. 

이것을 일반적인 $n$  에 대한 다항함수로 확장시켜서 생각하면 $$f(n)=a_0 + a_1 n + \cdots + a_d n^d \;\; (a_d >0)$$ 에 대하여 $$a_0 + a_1 n + a_2 n^2 + \cdots + a_d n^d \le \left ( |a_0| + |a_1| + |a_2| + \cdots + |a_n| \right ) n^d$$ 이므로 $c=  |a_0| + |a_1| + |a_2| + \cdots + |a_n| , \;\; n_0 = 1$ 로 결정하면 함수 $f(n)$ 은 $O \left (n^d \right )$ 로 표기할 수 있다. 

그렇다면 $O(n)$ 으로 표시되는 알고리즘과  $O \left ( n^2 \right ) $로 표시되는 알고리즘 중 어느 것이 더 좋다고 할 수 있을까? 당연히 $O(n)$ 으로 표현되는 알고리즘이 더 좋다고 할 수 있을 것이다. 단순화해서 생각하면 프로그램의 실행시간이 $n$ 에 비례하는가 $n^2$ 에 비례하는가의 문제이기 때문이다.

빅오 표기법에서는 이렇듯 함수의 증가 속도에 따라서 다음의 7가지 함수들을 사용한다. $$1, \;\; \log n, \;\; n, \;\; n^2 , \;\; n^3 , \;\; 2^n$$ 왼쪽에서부터 살펴보면, 상수함수, 로그함수, 선형함수, 로그 선형함수, 이차함수, 삼차함수, 지수함수가 된다. 이것들의 그래프를 보면 나열된 순서대로 증가 속도가 큰 것을 확인할 수 있다. 아래 함수들의 그래프를 보면 그 증가 속도의 대소관계를 파악하기 쉬울 것이다. 

다만 위 그래프에서 착각하지 말아야 할 것은 $n$ 의 값이 커지면 커질수록 $2^n$ 의 증가속도가 $n^3$ 의 증가속도보다 훨씬 빠르다는 것이다. $n=10$ 인 경우만 보더라도 $ 10^3 < 2^{10}$ 이고 그 이후로는 더욱더 큰 격차를 보이면서 $2^n$ 이 빠르게 증가한다. 실제로 위 7개 함수의 함숫값들을 비교하면 다음과 같다.

결국 위 함수들의 증가속도는 $n \to \infty$ 인 상황에서 비교하는 것이 맞다고 할 수 있다.

이와 같은 사실을 토대로 다음과 같은 결과를 얻을 수 있다.

• $5n^2 +3n \log n + 2n + 5$ is $O \left (n^2 \right )$

• $20n^3 +10n \log n +5$ is $ O \left (n^3 \right )$

• $3 \log n +2$ is $O(\log n)$

• $2^{n+2}$ is $O \left (2^n \right )$

참고로 다음과 같이  Big-Omega 와  Big-Theta 도 생각할 수 있다.

Big-Omega

함수 $f(n)$ 과 $g(n)$ 의 자연수를 양의 실수로 대응시키는 함수라고 할 때, 다음을 만족시키는 양의 상수 $c>0$ 와 정수 $n_0 \ge 1$ 이 존재하면 "$ f(n)$ is $\Omega (g(n))$" 이라고 쓰고, "$f(n)$ is big-Omega of $g(n)$" 으로 읽는다. $$f(n) \ge c g(n), \text{        for       } n \ge n_0$$

Big-Theta

함수 $f(n)$ 과 $g(n)$ 의 자연수를 양의 실수로 대응시키는 함수라고 할 때, 다음을 만족시키는 양의 상수 $c'>0, \; c''>0$ 와 정수 $n_0 \ge 1$ 이 존재하면 "$ f(n)$ is $\Theta (g(n))$" 이라고 쓰고, "$f(n)$ is big-Theta of $g(n)$" 으로 읽는다. $$ c'g(n) \le f(n) \le c'' g(n), \text{        for       } n \ge n_0$$

대충 감을 잡았겠지만 빅오는 알고리즘의 최악의 성능을, 빅오메가는 알고리즘의 최고의 성능을, 빅쎄타는 좀더 정확한 알고리즘의 성능을 표시해 준다. 이 중에서 빅오 표기법을 주로 사용하는 이유는 '가장 최악인 상황에서도 최소 이 정도의 성능은 보장된다' 라는 의미를 담고 있기 때문이다. 

<참고> Big-Oh Notation 실례