시간복잡도와 Big-O 표기법

프로그램이 “빠르다”고 말할 때, 우리는 보통 초 단위 실행 시간을 떠올린다. 하지만 실행 시간은 CPU·언어·컴파일러에 따라 제각각이라 알고리즘 자체를 비교하는 잣대로는 못 쓴다. 그래서 알고리즘의 성능은 입력 크기가 커질 때 연산 횟수가 어떻게 늘어나는가로 잰다. 이 증가율을 표기하는 언어가 Big-O다.

Big-O는 무엇을 재나

Big-O는 입력 크기 n이 커질 때 연산 횟수의 증가율을 나타낸다. 핵심은 두 가지 버림이다.

상수와 계수를 버린다. 3n + 100도, n도 모두 O(n)이다. n이 충분히 커지면 계수 3이나 상수 100은 증가 추세에 영향을 주지 못하기 때문이다.
최고차항만 남긴다. n² + n은 O(n²)다. n이 커질수록 n² 앞에서 n은 무시할 만큼 작아진다.

즉 Big-O는 “정확히 몇 번 도느냐”가 아니라 “규모가 커질 때 얼마나 빠르게 나빠지느냐”를 본다. 보통은 최악의 경우(worst case)를 기준으로 잡는다.

대표 복잡도의 감

자주 나오는 복잡도를 느린 순으로 세우면 대략 이렇다.

표기	이름	예
`O(1)`	상수	배열 인덱스 접근, 해시 조회
`O(log n)`	로그	이진 탐색
`O(n)`	선형	배열 한 번 훑기
`O(n log n)`	선형로그	병합·퀵 정렬
`O(n²)`	제곱	이중 반복문(모든 쌍 비교)
`O(2ⁿ)`	지수	부분집합 전부 나열

O(log n)이 빠른 이유는 매 단계마다 후보를 절반으로 줄이기 때문이다. n이 백만이어도 스무 번 남짓이면 끝난다.

코드로 보기 — 같은 문제, 다른 복잡도

“배열에서 합이 target인 두 수가 있는가”를 두 가지로 풀어 보자.

# O(n²) — 모든 쌍을 비교
def has_pair_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

이중 반복문이라 원소가 2배가 되면 연산은 약 4배가 된다. 같은 문제를 해시로 바꾸면:

# O(n) — 한 번 훑으며 필요한 짝을 해시로 확인
def has_pair_sum(nums, target):
    seen = set()
    for x in nums:
        if target - x in seen:
            return True
        seen.add(x)
    return False

target - x가 이미 지나온 값 중에 있는지를 set으로 O(1)에 확인한다. 전체를 한 번만 도니 O(n)이다. 알고리즘을 바꾸면 복잡도의 차원 자체가 내려간다는 점이 핵심이다.

코딩테스트에서의 감각

문제의 입력 크기 n을 보면 허용되는 복잡도를 거꾸로 가늠할 수 있다. 흔히 쓰는 어림값은 “한 계산 단위에서 대략 1초에 1억 번 정도 연산”이라는 관례인데, 언어·환경에 따라 편차가 크므로 절대적인 수치가 아니라 감을 잡는 용도로만 쓴다.

n ≤ 10⁶ 근처라면 O(n)이나 O(n log n)을 노려야 한다.
n ≤ 수천 정도면 O(n²)도 대체로 통과한다.
n ≤ 20 안팎이면 O(2ⁿ) 같은 완전 탐색도 시도해 볼 만하다.

그래서 문제를 받으면 코드를 짜기 전에 “이 입력 크기에서 어떤 복잡도까지 허용되나”를 먼저 어림하는 습관이 유용하다. Big-O는 결국, 짜기 전에 이 풀이가 시간 안에 들어올지를 가늠하게 해 주는 언어다.