빅오(Big-O) 시간복잡도 완벽 정리: 코딩테스트 필수 개념

코딩테스트에서 "통과"와 "시간 초과"를 가르는 핵심은 결국 시간복잡도입니다. 같은 문제를 풀어도 O(n²)로 짜면 터지고 O(n log n)으로 짜면 통과하죠. 빅오 표기법을 정확히 이해하면 코드를 제출하기 전에 통과 여부를 머릿속으로 가늠할 수 있습니다.

빅오 표기법이란?

빅오(Big-O)는 입력 크기 n이 무한히 커질 때 연산 횟수가 어떻게 증가하는지를 나타내는 상한(최악의 경우) 표기법입니다. 핵심 규칙 두 가지만 기억하세요.

• 상수항과 계수는 무시한다: 3n + 5 → O(n)
• 가장 큰 항만 남긴다: n² + n → O(n²)

즉 빅오는 "정확한 시간"이 아니라 "증가하는 추세"를 봅니다.

자주 나오는 복잡도 순서

빠른 것부터 느린 순서입니다.

표기법	이름	예시
O(1)	상수	배열 인덱스 접근, 해시 조회
O(log n)	로그	이진 탐색
O(n)	선형	배열 1회 순회
O(n log n)	선형로그	병합·퀵 정렬
O(n²)	제곱	이중 반복문
O(2ⁿ)	지수	부분집합 완전탐색
O(n!)	팩토리얼	순열 완전탐색

코드로 보는 복잡도

# O(1) - 입력 크기와 무관
def get_first(arr):
    return arr[0]

# O(n) - 한 번 순회
def total(arr):
    s = 0
    for x in arr:      # n번 반복
        s += x
    return s

# O(n^2) - 이중 반복문
def has_dup(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

로그가 등장하는 대표 예시는 이진 탐색입니다. 매 단계마다 탐색 범위가 절반으로 줄기 때문에 O(log n)이 됩니다.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

입력 크기로 복잡도 추측하기

대부분의 채점 환경은 1초에 약 1억(10⁸) 번 연산을 기준으로 합니다. 입력 n의 최대값을 보면 의도된 복잡도를 역추정할 수 있습니다.

n 최대	허용 복잡도
n ≤ 11	O(n!)
n ≤ 25	O(2ⁿ)
n ≤ 5,000	O(n²)
n ≤ 1,000,000	O(n log n)
n ≤ 100,000,000	O(n) 또는 O(log n)

함정: 빅오가 같아도 상수가 다르면 실제 속도는 크게 차이 납니다. 하지만 채점 기준선은 위 표로 잡고 시작하세요.

마무리 체크리스트

• 상수와 계수는 무시하고 최고차항만 본다
• 중첩 반복문 = 곱셈, 이어지는 반복문 = 덧셈(→ 최고차만 남김)
• 절반씩 줄면 log, 완전탐색이면 2ⁿ·n!
• 문제의 n 최댓값으로 목표 복잡도를 먼저 정한다

빅오는 외우는 게 아니라 코드를 보고 추세를 읽는 감각입니다. 문제를 풀 때마다 "이건 몇 번 도는가?"를 의식적으로 세어 보세요.