시간 안에 끝나는 알고리즘: 복잡도 점검하기

함수를 작성해서 테스트 데이터에 실행하면 잘 돌아갑니다. 그다음 프로덕션 데이터가 들어옵니다 — 500개가 아니라 500,000줄 — 그리고 요청 시간이 초과됩니다. 이런 일은 끊임없이 일어나며, 거의 항상 작은 규모에서는 합리적으로 보였던 코드 뒤에 숨어 있는 복잡도 문제입니다.

왜 당신의 랩톱이 거짓말을 했는가

O(n²) 알고리즘이 100개 항목에서 실행되면 10,000개 연산을 합니다. 어떤 머신에서든 순간입니다. 같은 알고리즘을 100,000개 항목에서 실행하면 100억 개 연산입니다 — 밀리초가 아니라 분 또는 시간입니다. n에서 n²로의 점프는 n이 커질 때까지 위험하게 느껴지지 않으며, 정확히 이것이 코드 리뷰와 로컬 테스팅을 빠져나가는 이유입니다.

고전적인 예제: 중첩 루프로 중복을 확인하기.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

이것은 O(n²)입니다. set으로 교체하세요:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

이제 O(n)입니다. Set 조회는 평균 O(1)이므로 전체 함수는 이차적이 아니라 선형으로 스케일합니다. 10,000개 항목에서 그것은 대략 1억 개 비교와 10,000개 비교 사이의 차이입니다.

최적화하기 전에 측정하세요

추측하지 마세요. timeit을 마이크로벤치마크에 사용하세요:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

더 큰 함수의 경우 cProfile로 프로파일하세요:

python -m cProfile -s cumulative myscript.py

cumtime 열을 확인하세요. 한 함수가 실행 시간의 90%를 차지하면 그것이 당신의 목표입니다. 병목이 아닌 코드를 최적화하는 것은 시간 낭비이며 이득 없이 복잡성을 추가합니다.

조용히 느려지는 일반적인 패턴

반복된 리스트 멤버십 확인. if x in my_list는 리스트에서 O(n)이지만 set 또는 dict에서 평균 O(1)입니다. 루프 내부에서 멤버십을 확인하고 있다면, 그 O(n) 확인이 O(n) 루프 내부에 있으면 전체적으로 O(n²)입니다. 리스트를 set으로 교체하면 다시 O(n)입니다.

루프에서 문자열 연결. Python에서 result += chunk를 문자열 루프 내부에서 실행하면 최악의 경우 O(n²)입니다. 문자열은 불변이고 각 연결이 전체를 복사하기 때문입니다. 대신 ''.join(chunks)을 사용하세요 — 문자열을 한 번에 만듭니다.

정렬할 필요가 없을 때 정렬하기. sorted()는 O(n log n)입니다. 각 반복마다 최댓값 또는 최솟값을 찾기 위해 루프 내부에서 호출하고 있다면 max()/min()을 사용하세요 (O(n)) 또는 더 나은 경우, 반복적으로 극값이 필요하면 heap (heapq)을 사용하세요. heapq.nlargest(k, data)는 O(n log k)이고, k가 작을 때 전체 리스트를 정렬하는 것보다 훨씬 저렴합니다.

메모이제이션 없는 재귀 함수. 순수 재귀 Fibonacci는 O(2ⁿ)입니다. 같은 부분 문제를 반복해서 재계산하기 때문입니다. functools.lru_cache를 추가하면 O(n)으로 떨어집니다:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

실제 코드에서 Big O를 빠르게 읽기

같은 입력에 대한 중첩 루프를 세세요 — 그것이 보통 당신의 지수입니다. 단일 루프는 O(n)입니다. 루프 안의 루프는 내부 루프의 범위가 축소되지 않으면 O(n²)입니다 (버블 정렬의 최적화된 형태처럼, 여전히 최악의 경우 O(n²)이지만 더 적은 비교). 이진 탐색 또는 병합 정렬처럼 문제를 반으로 나누는 재귀 호출은 O(log n) 또는 O(n log n)을 시사합니다. 순수 Fibonacci처럼 각 레벨에서 여러 호출로 분기하는 재귀 호출은 지수 시간을 시사합니다 — 메모이제이션이나 반복적 재작성이 필요하다는 강한 신호입니다.

좋은 습관: 중첩 루프나 사용자 대면 데이터에 대한 재귀를 작성하기 전에 프로덕션에서 n이 현실적으로 얼마나 커질 수 있는지 묻거나 테스트 파일에서가 아닙니다. n이 6자리에 도달할 수 있다면 O(n²) 솔루션은 배포하기 전에 두 번째로 확인할 필요가 있습니다.

복잡도 분석, 정렬 알고리즘, 프로파일링 도구에 대한 자세한 내용은 Korra Studio의 Python 및 Computer Science 섹션을 확인하세요.