알고리즘 복잡도(점근적 복잡도) 기본 개념 다지기

알고리즘의 복잡도란 알고리즘이 소모하는 시간이나 공간을 분석하기 위한 것입니다. 시간과 관련된 것은 시간 복잡도(time complexity), 공간과 관련된 것은 메모리 복잡도(memory complexity)라고 하죠. 최근에는 데이터를 저장할 수 있는 메모리의 발전으로 메모리 복잡도보단 시간 복잡도를 더 중요시하게 여깁니다.

그리고 알고리즘 복잡도는 점근적 복잡도(Asysmptotic Complexity)에 대해서 생각합니다. 이는 곧 정확한 복잡도를 구한다기보다는 입력의 크기가 충분히 클 경우에 대해 생각하는 것입니다. 본 글에서는 크게 3가지를 소개하겠습니다.

1. $O$(빅 오)
- 최악의 경우
2. $\Omega$(빅 오메가)
- 최상의 경우
3. $\Theta$(빅 세타)
- 평균의 경우
=> 모두 집합을 가리킴

n: 데이터 입력 크기

먼저 $O$에 대해서 말씀드리면, 최고차항의 차수가 $f(n)$보다 작거나 같은 모든 함수를 말합니다. 예를 들어, $O_{(n^2)}$라고 표기된 것은 최고차항의 차수가 2차 이하인 모든 함수를 포함하는 집합입니다. $O$는 최고차항의 수가 작거나 같은 함수를 가리키기 때문에 최악의 경우를 표시한다고 이해할 수 있습니다.

다음은, $\Omega$로 최고차항의 차수가 $f(n)$보다 크거나 같은 모든 함수를 말합니다. 위의 동일한 예시인 $O_{(n^2)}$는 여기서 최고차항의 차수가 2차 이상인 모든 함수를 포함하는 집합입니다. 크거나 같다고 했기 때문에 최상의 경우를 표시한다고 이해할 수 있습니다.

마지막 $\Theta$는 최고차항의 차수가 $f(n)$과 동일한 모든 함수를 말합니다. 따라서 $O_{(n^2)}$의 경우 최고차항의 차수가 2차인 모든 함수를 포함하는 집합이 되죠. 논리적으로 보면 $\Theta$ 집합은 $O$ 집합과 $\Omega$ 집합의 교집합($\approx$ 평균)이라 볼 수 있겠습니다.

아래 그림을 보면 (a)는 $O$를, (b)는 $\Omega$를, (c)는 $\Theta$를 가리키고 있으며, $c g(n)$은 임의의 함수를 나타냅니다.

<출처: 딩동딤동 블로그>

아래 예시 코드를 보며 위의 3가지 점근적 표기법을 살펴보도록 합시다.

n에 관계없이 상수시간 소요
표기법: $\Omega(1)$, $O(1)$, $\Theta(1)$ 모두 가능
베스트 표기법: $\Theta(1)$

from typing import List
def notation(L: List, n):
    k = n / 2
    return L[k]

항상 n에 비례하는 시간 소요
표기법: $\Omega(n)$, $O(n)$, $\Theta(n)$ 모두 가능
베스트 표기법: $\Theta(n)$

def notation(L:List, n):
    sum = 0
    for i in range(n):
        sum += L[i]
    return sum

최악의 경우 n에 비례하는 시간 소요(n이 매우 큰 홀수인 경우)
최선의 경우 상수 시간 소요(n이 짝수인 경우)
표기법: $\Omega(1)$, $O(n)$
최선의 경우 $\Theta(1)$, 최악의 경우 $\Theta(n)$

def notation(L:List, n):
    sum = 0
    if n % 2 != 0:
        for i in range(n):
            sum += L[i]
    return sum

아래는 함수에 따른 시간 복잡도, 그 중에서도 $O$ 표기법을 나타낸 그래프입니다. 가장 적은 리소스를 소모하는 것은 $log_2(n)$이고, 가장 많은 리소스를 소모하는 것은 $n!$인 것을 확인할 수 있습니다. 그래프 관점에서만 보자면 기울기가 급격하게 증가하는 것과 가장 변화가 없는 것을 보면 되겠죠.