[자료구조 알고리즘] 빅오(Big-O) 표기법

빅오란, 알고리즘의 성능을 수학적으로 표현해주는 표기법이다. 이를 이용하여 알고리즘의 시간과 공간복잡도를 표현할 수 있다.

 

1. O(1), constant time

입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 의미한다.

def array_zero(n):
    return (n[0] == 0)

위 함수를 보면 입력 데이터인 n의 0번째 인덱스의 숫자가 0이면 True를 0이 아니면 False를 반환한다. 이는 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸린다.

 

2. O(n), linear time

입력 데이터의 크기와 비례하여 처리 시간이 걸리는 알고리즘을 의미한다.

def array_print(n):
    for i in range(n):
    	print(i)

위 함수를 보면 n이 하나 늘어날수록 처리시간이 1 늘어나는 것을 알 수 있다.

 

3. O(n^2), quadratic time

def array_sqaure(n):
    for i in range(n):
    	for j in range(n):
        	print(i + j)

위 함수를 보면 첫 번째 loop를 돌면서 그 안에서 한 번 더 n번 loop를 돌기 때문에 처리시간은 n^2가 되는 것이다. 따라서 데이터를 더 많이 추가함에 따라 처리시간이 수직상승하게 된다.

 

4. O(nm), quadratic time

def array_nm(n, m):
    for i in range(n):
    	for j in range(m):
            	print(i+j)

위에서 봤던 O(n^2)와 유사하다. 하지만 n을 두 번 돌리는 것이 아니라 m을 n만큼 돌리는 것이다.

 

5. O(n^3), polynomial / cubic time

def array_cubic(n):
    for i in range(n):
    	for j in range(n):
            	for k in range(n):
                    	print(i + j + k)

loop를 3번 돌리면 O(n^3)이 된다. O(n^2)와 비교하였을 때 O(n^3)는 데이터의 크기가 늘어남에 따라 처리 시간이 급격하게 늘어나게 된다.

 

6. O(2^n), exponential time

O(n^2) 알고리즘과 O(2^n) 알고리즘은 비슷하게 생겼으나 완전히 다르기 때문에 헷갈리지 않도록 유의해야 한다. O(2^n) 알고리즘의 대표적인 예시는 재귀함수를 이용한 피보나치 수열이다.

def fibo(n, r):
    if n <= 0: return 0
    elif n == 1: 
    	return r[n] = 1
    return r[n] = fibo(n-1, r) + fibo(n-2, r)

O(2^n) 알고리즘은 O(n^2), O(n^3) 알고리즘과 비교하여 데이터의 크기가 늘어남에 따라 처리시간이 현저하게 늘어나게 된다.

 

7. O(m^n), exponential time

6번 알고리즘에서 2 대신 m을 사용하고 싶다면 위와 같은 알고리즘으로 표기하면 된다.

 

8. O(logn)

O(logn)의 대표적인 예시는 이진탐색이다. 즉, 한 번 처리가 진행될 때마다 검색해야 하는 데이터의 양이 절반씩 떨어지는 알고리즘을 의미한다. 따라서 순차검색과 비교하여 처리 속도가 현저하게 빠르다.

def binary(k, arr, s, e):
    if s > e: return -1
    m = (s + e) / 2
    if arr[m] == k: return m
    elif arr[m] > k: return binary(k, arr, s, m-1)
    else:
    	return binary(k, arr, m+1, e)

 

9. O(sqrt(n))

O(sqrt(n))은 입력 데이터의 크기가 100일 때, 처리시간은 10만큼 걸리는 알고리즘이다.

 

10. Drop constants

마지막으로 빅오 표기법에서 중요한 한 가지 개념이다. 빅오 표기법에서는 상수는 과감하게 버린다.

def drop_constant(n):
    for i in range(n):
    	print(i)
    for i in range(n):
    	print(i)

위 코드의 시간복잡도는 얼마일까? n만큼을 2회 돌리기 때문에 O(2n)이지만 O(n)으로 간주한다. 왜냐하면 빅오 표기법은 실제 알고리즘의 러닝타임을 재기 위한 것이 아니라 장기적으로 데이터가 증가함에 따른 처리시간의 증가율을 예측하기 위한 표기법이기 때문이다. 상수는 고정된 숫자이기 때문에 증가율을 측정할 때 고정된 상수만큼 영향을 미치기 때문에 증가하지 않는 숫자는 신경쓰지 않겠다는 것이다.

 

마지막으로 위에서 본 빅오 표기법의 알고리즘의 데이터의 크기에 따른 처리시간의 그래프를 요약하면 아래와 같다.

[출처] https://velog.io/@qksud14/Algorithm-BigO

 

 

위 포스팅은 https://www.youtube.com/watch?v=6Iq5iMCVsXA&t=391s 을 참고하여 작성하였습니다.