빅오 표기법 예제로 쉽게 이해하기

빅오가 해결하는 문제

프로그램 실행 시간을 초 단위로 재면 한 대의 컴퓨터, 한 가지 언어, 한 가지 입력에 대해서만 알 수 있습니다. 빅오는 더 유용한 질문에 답합니다. 입력이 10배 커지면 알고리즘이 하는 일은 얼마나 늘어날까요? 일이 10배 늘어나는 알고리즘과 100배 늘어나는 알고리즘은 규모가 커질수록 크게 차이가 납니다.

형식적으로는 모든 n ≥ n₀에 대해 f(n) ≤ c · g(n)을 만족하는 상수 c와 n₀가 있으면 f(n)은 O(g(n))입니다. 쉽게 말해, n이 충분히 크면 상수 배를 무시했을 때 g가 f 증가 속도의 상한이 된다는 뜻입니다.

• n은 입력의 크기입니다. 리스트의 길이, 문자열의 글자 수, 그래프의 노드 수 등이 해당합니다.
• 시간 복잡도는 기본 연산(비교, 대입, 산술 연산)의 횟수를 셉니다.
• 공간 복잡도는 입력 자체를 제외하고 추가로 사용하는 메모리를 셉니다.

식을 단순화하는 방법

단계 수를 n의 함수로 구한 다음 두 가지 규칙을 적용합니다. 상수 계수를 버리고, 가장 지배적인 항만 남깁니다.

독립된 입력이 두 개인 알고리즘은 둘 다 남깁니다. 길이 n인 리스트를 돌고 나서 길이 m인 리스트를 도는 것은 O(n + m)이고, 반복문 안의 반복문은 O(n · m)입니다. 빅오에서는 로그의 밑이 중요하지 않습니다. log₂ n과 log₁₀ n은 상수 배만 차이 나기 때문입니다.

주요 복잡도 종류

대략적인 기준은 다음과 같습니다. 요즘 컴퓨터에서 단순한 반복문은 파이썬에서 초당 수천만 번, 컴파일 언어에서는 그보다 훨씬 많이 기본 연산을 실행할 수 있습니다. 따라서 O(n log n)은 수백만 개 항목에도 충분하고, O(n²)은 수만 개 근처부터 느려지며, O(2ⁿ)은 40~60개만 넘어도 사실상 불가능합니다.

파이썬 코드에서 복잡도 읽기

반복문을 보세요. 입력에 대한 반복문 하나는 O(n)입니다. 같은 입력에 대해 반복문 안에 반복문이 있으면 O(n²)입니다. 매번 남은 범위를 절반으로 줄이는 반복문은 O(log n)입니다.

def first(items):            # O(1): one step, whatever the size
    return items[0]
def total(items):            # O(n): touches each item once
    s = 0
    for x in items:
        s += x
    return s
def has_duplicate(items):    # O(n^2): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False
def halvings(n):             # O(log n): n is halved each step
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps
print(first([7, 8]), total([1, 2, 3]), has_duplicate([1, 2, 1]), halvings(1024))
# 7 6 True 10

라이브러리 호출에도 비용이 있습니다. x in some_list는 O(n), x in some_set은 평균 O(1), list.insert(0, x)는 모든 요소가 밀리므로 O(n), sorted()는 O(n log n)입니다. O(n) 연산을 n번 호출하는 반복문은 겉보기에는 반복문 하나여도 O(n²)입니다.

def has_duplicate_fast(items):   # O(n) time, O(n) extra space
    seen = set()
    for x in items:
        if x in seen:            # average O(1) set lookup
            return True
        seen.add(x)
    return False
print(has_duplicate_fast([3, 1, 4, 1, 5]))   # True
print(has_duplicate_fast(list(range(10))))   # False

최선, 평균, 최악의 경우

같은 크기의 입력이라도 입력에 따라 알고리즘이 하는 일의 양이 달라질 수 있으므로, 복잡도는 보통 세 가지 경우로 나누어 말합니다.

그냥 "X의 복잡도"라고만 말하면 보통 최악의 경우를 뜻하며, 해시 테이블과 퀵 정렬은 평균적인 경우를 뜻합니다. 분할 상환 비용이라는 네 번째 개념도 있습니다. 파이썬 리스트에 요소를 추가하는 일은 저장 공간을 늘릴 때 가끔 O(n)이지만, 여러 번 추가한 평균으로는 O(1)입니다.

빅오, 빅오메가, 빅세타

엄밀히 말하면 O는 상한일 뿐이므로 O(n) 알고리즘은 O(n²)이기도 합니다. 일상적으로는 빅오라고 쓰면서도 자신이 아는 가장 정확한 한계를 뜻하는 경우가 많으며, 그것을 나타내는 것이 Θ입니다.

흔한 실수

• 리스트에 in을 쓰거나 items[1:]로 슬라이싱하는 등 내장 연산의 비용을 잊는 경우입니다. 슬라이싱은 복사하므로 복사한 요소 k개에 대해 O(k)입니다.
• 재귀 호출을 잘못 세는 경우입니다. n − 1에 대해 자신을 두 번 호출하는 함수는 O(n)이 아니라 O(2ⁿ)입니다.
• 공간을 무시하는 경우입니다. 크기 n인 새 리스트를 만들거나 깊이 n의 재귀를 쓰면 메모리가 O(n) 듭니다.
• O(2n)이나 O(n + 5)처럼 쓰는 경우입니다. 둘 다 O(n)으로 단순화됩니다.