복잡도 분석

빅오 표기는 저장한 항목 수 n 이 늘 때 비용이 어떻게 커지는지 알려 줍니다. 기본 자료구조에서 흥미로운 점은 같은 연산이 어떤 구조에서는 O(1), 다른 구조에서는 O(n)이라는 것, 그리고 일부 O(1)은 보장이 아니라 평균이거나 분할 상환 값이라는 것입니다.

연산 비용 한눈에 보기

스택과 큐는 이 구조들의 사용법을 제한한 것입니다. 동적 배열 위의 스택은 push와 pop이 분할 상환 O(1)이고, 원형 버퍼나 연결 리스트 위의 큐는 넣기와 빼기가 O(1)입니다.

분할 상환 O(1) 추가

가득 찬 동적 배열에 한 번 추가하면 n 개를 모두 복사하므로 O(n)입니다. 하지만 두 배씩 늘리면서 n 번 추가하면 복사 횟수는 1 + 2 + 4 + ... + n/2 + n 으로 2n 보다 작습니다. 전체 작업이 O(n)이므로 추가 한 번당 분할 상환 O(1)입니다.

늘리는 비율이 중요합니다. 매번 일정한 칸 수(예: 10칸)만 늘리면 복사는 10 + 20 + 30 + ... 이 되어 전체가 O(n 제곱)입니다. 1보다 큰 일정한 배수로 늘리기만 하면 분할 상환 O(1)이 유지되며, 라이브러리는 메모리와 속도를 저울질해 1.5배, 2배, 또는 CPython처럼 조금씩 넉넉하게 잡는 방식을 고릅니다.

def total_copies(n, grow):
    size, cap, copies = 0, 1, 0
    for _ in range(n):
        if size == cap:
            copies += size
            cap = grow(cap)
        size += 1
    return copies

n = 100_000
print("x2   :", total_copies(n, lambda c: c * 2))       # 약 1.3 * n
print("x1.5 :", total_copies(n, lambda c: c + c // 2 + 1))
print("+10  :", total_copies(n, lambda c: c + 10))      # 약 n * n / 20

해시 테이블: 평균과 최악

버킷이 m 개, 키가 n 개면 적재율은 alpha = n / m 입니다. 해시 함수가 키를 고르게 흩뜨린다면 사슬의 기대 길이는 alpha 이고, 찾기 비용은 O(1 + alpha)입니다. alpha 를 일정 값 아래로 유지하면(Java HashMap 은 0.75, C++ std::unordered_map 은 기본 1.0) 평균 O(1)이 됩니다. 크기를 늘릴 때는 O(n)이 들지만, 배열이 자랄 때처럼 삽입 한 번당 분할 상환 O(1)입니다.

최악은 O(n)입니다. 모든 키가 한 버킷에 몰리면 테이블은 리스트가 되어 버립니다. 해시 함수가 나쁘거나, 일부러 충돌하도록 만든 입력(해시 플러딩)이 들어오면 이런 일이 생깁니다. 그래서 Python은 프로세스마다 문자열 해시를 무작위화하고, Java HashMap 은 아주 긴 사슬을 균형 트리로 바꿔 최악을 O(log n)으로 낮춥니다.

직접 재 보기

복잡도 표는 타이머로 쉽게 확인할 수 있습니다. 앞에서 빼기가 대표적인 함정입니다.

from collections import deque
from timeit import timeit

def drain_list(n):
    items = list(range(n))
    while items:
        items.pop(0)          # 남은 항목을 모두 한 칸씩 당김

def drain_deque(n):
    items = deque(range(n))
    while items:
        items.popleft()       # 인덱스 하나만 움직임

n = 100_000
print("list.pop(0)    ", timeit(lambda: drain_list(n), number=1))
print("deque.popleft()", timeit(lambda: drain_deque(n), number=1))

리스트 쪽은 전체가 제곱 시간이라 이 크기에서도 백 배 넘게 느린 경우가 흔합니다. 포함 검사에서는 해시 테이블의 이점이 드러납니다.

from timeit import timeit

items = list(range(10_000))
as_set = set(items)
probes = range(0, 20_000, 7)
print("list:", timeit(lambda: sum(p in items for p in probes), number=1))
print("set :", timeit(lambda: sum(p in as_set for p in probes), number=1))

Python 내장 타입

공간

다섯 구조 모두 O(n) 공간을 쓰지만 상수가 다릅니다. 동적 배열은 막 늘어난 직후 필요한 칸의 두 배 가까이를 잡고 있을 수 있습니다. 이중 연결 리스트는 항목마다 포인터 두 개를 저장하므로, 64비트 환경에서는 값과 별도로 16바이트가 더 듭니다. 해시 테이블은 적재율을 0.75나 1 같은 상한 아래로 묶어 두므로 빈 버킷이 늘 많고, 분리 연결법은 항목마다 노드를 하나 더 만듭니다.

정리

배열은 O(1) 인덱싱과 분할 상환 O(1) 추가를, 연결 구조는 알고 있는 위치에서 O(1) 끼워 넣기를, 해시 테이블은 평균 O(1) 키 연산과 최악 O(n)을 줍니다. 늘리는 비율이 기하급수적이고 해시 함수가 키를 잘 흩뜨리기만 하면 분할 상환과 평균 값은 실무에서 믿을 만합니다. 의심스러우면 직접 재 봅니다.