복잡도 분석의 개념

복잡도 분석은 알고리즘이 입력 크기에 따라 시간과 메모리를 얼마나 더 쓰는지를 따지는 방법입니다. "이 코드는 0.3초 걸린다"는 측정값은 컴퓨터, 언어, 입력 데이터에 따라 달라지지만, "입력이 두 배가 되면 실행 시간이 네 배가 된다"는 성질은 어느 환경에서나 거의 그대로 유지됩니다. 복잡도 분석은 바로 이 성장의 모양을 다룹니다. 이 장에서는 입력 크기, 점근 표기(O, Ω, Θ), 최선·평균·최악의 경우, 그리고 앞으로 계속 쓰게 될 용어를 정리합니다.

입력 크기 n

분석은 입력 크기를 정하는 데서 시작합니다. 리스트라면 원소 수, 문자열이라면 길이가 보통 n입니다. 그래프처럼 정점 수 V와 간선 수 E 두 변수를 함께 써야 하는 경우도 있고, 두 문자열을 비교하는 문제라면 각 길이 m과 n을 따로 둡니다.

정수 하나를 입력으로 받는 함수는 조심해야 합니다. 입력 크기는 값 자체가 아니라 그 수를 적는 데 필요한 자릿수(비트 수)입니다. 그래서 2부터 √n까지 나눠 보는 소수 판별은 값 n에 대해서는 O(√n)이지만, 비트 수 b에 대해서는 O(2^(b/2))인 지수 시간입니다.

점근 표기: O, Ω, Θ

점근 표기는 n이 충분히 커졌을 때 함수가 자라는 속도를 비교하는 말입니다.

• Big-O(상한): 어떤 양의 상수 c와 시작점 n0이 있어서 n ≥ n0인 모든 n에 대해 f(n) ≤ c·g(n)이면 f(n) = O(g(n))이라고 씁니다. "g보다 빠르게 자라지 않는다"는 뜻입니다.
• Big-Omega(하한): 같은 조건에서 f(n) ≥ c·g(n)이면 f(n) = Ω(g(n))입니다. "적어도 g만큼은 자란다"는 뜻입니다.
• Big-Theta(딱 맞는 차수): O와 Ω를 모두 만족하면 f(n) = Θ(g(n))입니다. 성장 속도가 g와 같은 차수라는 뜻입니다.

예를 들어 f(n) = 3n² + 5n + 20은 n ≥ 1에서 3n² ≤ f(n) ≤ 28n²이므로 Θ(n²)입니다. O(n³)이라고 써도 틀리지는 않지만 느슨한 상한이라 정보가 적습니다. 실무에서 "이 함수는 O(n²)이다"라고 말할 때는 대개 Θ의 뜻으로 씁니다.

상수와 낮은 차수 항을 버리는 이유는 n이 커질수록 가장 높은 차수 항이 전체를 좌우하기 때문입니다. 아래 코드로 비율을 직접 확인할 수 있습니다.

def f(n):
    return 3 * n * n + 5 * n + 20

for n in (10, 100, 1_000, 10_000):
    print(n, f(n), round(f(n) / (n * n), 4))
# 10 370 3.7
# 100 30520 3.052
# 1000 3005020 3.005
# 10000 300050020 3.0005

비율이 상수 3으로 다가갑니다. 즉 f는 결국 n²의 상수배처럼 움직이고, 상수 3은 하드웨어나 구현에 따라 바뀌는 값이므로 표기에서 뺍니다.

경우와 한계는 다른 축입니다

흔한 오해는 "O는 최악의 경우, Ω는 최선의 경우"라는 생각입니다. 실제로는 두 가지가 서로 다른 질문입니다.

• 어떤 입력을 볼 것인가: 최선의 경우, 평균적인 경우, 최악의 경우
• 그 실행 시간을 어떻게 표현할 것인가: 상한 O, 하한 Ω, 딱 맞는 차수 Θ

선형 탐색은 찾는 값이 맨 앞에 있으면 비교 1번으로 끝나고(최선 Θ(1)), 없거나 맨 끝에 있으면 n번 비교합니다(최악 Θ(n)). 값이 리스트 안에 고르게 있다고 가정하면 평균 비교 횟수는 (n + 1) / 2이고, 이것도 Θ(n)입니다.

def linear_search(items, target):
    comparisons = 0
    for i, x in enumerate(items):
        comparisons += 1
        if x == target:
            return i, comparisons
    return -1, comparisons

data = [7, 3, 9, 4, 1]
print(linear_search(data, 7))   # (0, 1)  최선의 경우
print(linear_search(data, 1))   # (4, 5)  끝에 있는 경우
print(linear_search(data, 8))   # (-1, 5) 없는 경우 = 최악

보통은 최악의 경우를 기준으로 말합니다. 사용자가 어떤 입력을 넣을지 모르므로 "어떤 입력이 와도 이 이상은 걸리지 않는다"는 보장이 가장 쓸모 있기 때문입니다.

시간만이 아니라 공간도

공간 복잡도는 알고리즘이 쓰는 추가 메모리가 입력 크기에 따라 어떻게 자라는지를 봅니다. 입력 자체를 빼고 계산한 것을 보조 공간(auxiliary space)이라고 부릅니다. 같은 문제라도 메모리를 더 써서 시간을 줄이는 선택이 자주 나옵니다.

def has_duplicate_slow(items):      # 시간 O(n²), 보조 공간 O(1)
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate_fast(items):      # 시간 O(n) 평균, 보조 공간 O(n)
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

언제 쓰는가

• 구현하기 전에 여러 방법 가운데 입력 규모에 맞는 것을 고를 때
• 코딩 테스트에서 제한 시간과 입력 범위를 보고 필요한 차수를 거꾸로 추정할 때
• 코드 리뷰에서 반복문 안의 in list, 반복되는 정렬처럼 숨은 비용을 찾을 때
• 데이터가 늘었을 때 서비스가 견딜 수 있는지 미리 가늠할 때

용어 정리

정리

• 복잡도 분석은 절대 시간이 아니라 입력 크기에 따른 성장의 모양을 봅니다.
• O는 상한, Ω는 하한, Θ는 둘 다를 뜻하며, 상수와 낮은 차수 항은 버립니다.
• 최선·평균·최악은 "어떤 입력인가"의 문제이고, O·Ω·Θ와는 다른 축입니다.
• 시간과 공간은 서로 맞바꿀 수 있으므로 둘을 함께 따져야 합니다.