Big-O 표기법 — 성능을 숫자로 말하기

이 토픽을 마치면

Big-O 표기법이 무엇인지 이해하고, 코드를 보고 시간 복잡도를 추정할 수 있으며, O(1) / O(n) / O(n²) / O(log n)의 차이를 설명할 수 있습니다.

왜 Big-O가 필요한가

"이 코드 느린데요" — 얼마나 느린지, 데이터가 늘면 얼마나 더 느려지는지 말할 수 있어야 합니다. Big-O는 입력 크기(n)에 따라 연산 횟수가 어떻게 증가하는지를 표현하는 표기법입니다.

실행 시간을 초 단위로 측정하는 것이 아닙니다. 컴퓨터 성능에 따라 초 단위는 달라지니까요. Big-O는 증가 패턴을 말합니다.

O(1) — 상수 시간

입력 크기와 관계없이 항상 같은 시간이 걸립니다.

def get_first(items):
    return items[0]  # 100개든 100만 개든 1번

# 딕셔너리 조회도 O(1)
user = {"name": "김훈"}
user["name"]  # 해시 계산 → 바로 접근

데이터가 10배로 늘어도 시간은 그대로입니다.

O(n) — 선형 시간

입력 크기에 비례해서 시간이 늘어납니다.

def find_max(items):
    max_val = items[0]
    for item in items:      # n번 반복
        if item > max_val:
            max_val = item
    return max_val

리스트가 100개면 100번, 100만 개면 100만 번 비교합니다. 데이터가 10배 늘면 시간도 10배 늘어납니다. for 루프 1개가 전체를 순회하면 보통 O(n)입니다.

O(n²) — 제곱 시간

중첩 루프가 대표적입니다.

def has_duplicate(items):
    for i in range(len(items)):         # n번
        for j in range(i + 1, len(items)):  # 최대 n번
            if items[i] == items[j]:
                return True
    return False

100개면 약 5,000번, 1,000개면 약 500,000번, 10,000개면 약 50,000,000번입니다. 데이터가 10배 늘면 시간이 100배 늘어납니다. 이것이 O(n²)가 위험한 이유입니다.

# O(n) 방식으로 개선 — set 활용
def has_duplicate_fast(items):
    seen = set()
    for item in items:       # n번
        if item in seen:     # set 검색 O(1)
            return True
        seen.add(item)
    return False

같은 문제를 O(n)으로 풀면, 10,000개에서 50,000,000번이 10,000번으로 줄어듭니다.

O(log n) — 로그 시간

매 단계마다 탐색 범위가 절반으로 줄어듭니다. 이진 탐색이 대표적입니다.

def binary_search(sorted_list, target):
    low, high = 0, len(sorted_list) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1        # 왼쪽 절반 버림
        else:
            high = mid - 1       # 오른쪽 절반 버림
    
    return -1  # 못 찾음

100만 개에서 최대 20번 비교로 찾습니다(log₂(1,000,000) ≈ 20). O(n)이면 100만 번인데, O(log n)이면 20번입니다. 단, 정렬된 데이터에서만 작동합니다.

한눈에 비교

O(n²)는 n이 10,000만 넘어도 실용적이지 않습니다. O(n log n)은 효율적인 정렬 알고리즘(merge sort, quick sort)의 복잡도입니다.

Big-O를 읽는 핵심 규칙

1. 상수는 버린다: O(3n) = O(n), O(100) = O(1)
2. 낮은 차수는 버린다: O(n² + n) = O(n²) — n이 크면 n²가 n을 압도
3. 최악의 경우를 본다: 리스트에서 검색할 때, 첫 번째에 있으면 O(1)이지만 Big-O는 마지막에 있는 최악을 기준으로 O(n)

이 3가지 규칙이면 대부분의 코드에서 Big-O를 추정할 수 있습니다.

핵심 정리

Big-O는 "이 코드가 데이터 10배에서도 살아남는가?"를 판단하는 도구입니다. 완벽한 계산보다 패턴을 인식하는 것이 중요합니다 — for 1개면 O(n), 중첩 for면 O(n²), 절반씩 줄이면 O(log n). 면접에서 자주 묻는 주제이기도 하지만, 그보다 실무에서 "왜 이 API가 데이터 많으면 느려지는지" 원인을 찾는 데 직접적으로 쓰입니다.