복잡도 분석 안내서 · 6/6

실무 활용

복잡도 분석은 시험 문제에만 쓰이는 도구가 아닙니다. 데이터가 열 배로 늘었을 때 서비스가 버틸지, 어떤 자료 구조를 고를지, 성능 문제의 원인이 어디인지 판단할 때 늘 바탕이 됩니다. 이 장에서는 실제 시스템에서 복잡도가 드러나는 곳과 자주 빠지는 함정, 그리고 더 읽을거리를 정리합니다.

표준 라이브러리의 비용 알기

같은 일을 하는 코드라도 어떤 자료 구조를 쓰는지에 따라 차수가 달라집니다. Python의 주요 연산 비용은 다음과 같습니다.

연산	`list`	`dict` / `set`	`collections.deque`
끝에 추가	상환 `O(1)`	`O(1)` 평균	`O(1)`
앞에 추가·삭제	`O(n)`	해당 없음	`O(1)`
포함 여부(`in`)	`O(n)`	`O(1)` 평균	`O(n)`
인덱스로 접근	`O(1)`	해당 없음	양 끝 `O(1)`, 가운데 `O(n)`
정렬(`sorted`)	`O(n log n)`	해당 없음	해당 없음

큐를 리스트로 만들고 pop(0)을 반복하면 매번 원소를 앞으로 당기느라 전체가 O(n²)이 됩니다. deque.popleft()로 바꾸면 O(n)입니다.

from collections import deque

def drain_list(n):
    q = list(range(n))
    while q:
        q.pop(0)          # 매번 O(n)

def drain_deque(n):
    q = deque(range(n))
    while q:
        q.popleft()       # O(1)

데이터베이스와 인덱스

인덱스가 없는 열로 검색하면 데이터베이스는 표 전체를 훑습니다(O(n)). B-트리 인덱스를 두면 조회가 O(log n)으로 줄어듭니다. 대신 쓰기마다 인덱스도 고쳐야 하므로 쓰기 비용과 저장 공간이 늘어납니다. 실행 계획(EXPLAIN)에서 전체 스캔이 보이면 복잡도 관점에서 먼저 의심할 곳입니다.

애플리케이션 쪽의 N+1 쿼리도 같은 문제입니다. 목록 n개를 가져온 뒤 항목마다 쿼리를 하나씩 더 보내면, 쿼리 하나의 왕복 시간이 상수라도 전체는 n에 비례해 늘어납니다. 한 번의 조인이나 IN (...) 묶음 조회로 바꾸면 왕복 수가 상수가 됩니다.

# N+1: 사용자마다 쿼리 한 번씩
for user in users:
    orders = db.query("SELECT * FROM orders WHERE user_id = ?", user.id)

# 묶음 조회: 쿼리 한 번
ids = [user.id for user in users]
placeholders = ", ".join("?" * len(ids))
orders = db.query(f"SELECT * FROM orders WHERE user_id IN ({placeholders})", *ids)

평균과 최악이 다른 곳: 해시와 정규식

해시 테이블의 O(1)은 평균일 뿐이고, 많은 키가 같은 버킷에 몰리면 최악 O(n)이 됩니다. 공격자가 일부러 충돌하는 키를 보내 서버를 느리게 만드는 해시 플러딩(hash flooding) 공격이 실제로 있었고, 그래서 Python은 문자열 해시에 실행마다 바뀌는 무작위 값을 섞고, Java의 HashMap은 충돌이 많은 버킷을 균형 트리로 바꿉니다.

정규식도 비슷합니다. 역추적 방식의 엔진에서 (a+)+$ 같은 패턴은 맞지 않는 입력에서 경우의 수가 지수적으로 늘어 서버를 멈추게 할 수 있습니다(ReDoS). 사용자 입력을 받는 정규식은 중첩된 반복을 피하고 입력 길이를 제한합니다.

import re
import time

pattern = re.compile(r"(a+)+$")
for n in (18, 20, 22):
    text = "a" * n + "!"
    start = time.perf_counter()
    pattern.match(text)
    print(n, f"{time.perf_counter() - start:.3f}s")   # n이 2 늘 때마다 약 4배

자주 빠지는 함정

상수를 무시하다 작은 입력에서 오판하기: n이 수십 이하라면 O(n²) 삽입 정렬이 O(n log n) 정렬보다 빠를 수 있습니다. 실제 정렬 라이브러리(Timsort, introsort)가 작은 구간에 삽입 정렬을 쓰는 이유입니다.
메모리 계층 무시하기: 같은 O(n)이라도 배열을 차례로 읽는 코드는 연결 리스트를 따라가는 코드보다 캐시 덕분에 몇 배 빠릅니다.
문자열을 반복해서 이어 붙이기: 언어와 구현에 따라 O(n²)이 될 수 있으므로 조각을 모아 "".join(parts)로 합칩니다.
측정 없이 추측하기: 병목은 예상과 다른 곳에 있을 때가 많습니다. cProfile 같은 프로파일러로 먼저 확인합니다.

더 읽을거리

정리

표준 라이브러리 연산의 비용을 알아 두면 pop(0)이나 in list 같은 숨은 O(n)을 피할 수 있습니다.
인덱스, 묶음 조회처럼 실무의 많은 성능 개선은 차수를 한 단계 낮추는 일입니다.
평균과 최악이 다른 연산은 공격이나 이상 입력에서 최악이 드러날 수 있음을 기억합니다.
차수는 출발점이고, 상수와 메모리 계층은 측정으로 확인합니다.

이 장에 대해 질문이 있나요?