복잡도와 빅오: 느린 코드를 알아보는 눈

같은 답을 내는 코드가 데이터 1,000개에서는 똑같이 빠르다가 100만 개에서는 1초와 몇 시간으로 갈리는 이유를 따져요. 실행 시간 대신 연산 횟수의 증가율을 보는 법, 빅오로 줄여 쓰는 규칙, O(1)부터 O(2ⁿ)까지 자주 만나는 복잡도와 두 배 실험, 코드에서 복잡도를 읽는 법과 in이나 pop(0)처럼 한 줄에 숨은 반복을 찾는 법을 직접 세어 확인해요. 이진 탐색의 로그, 최선과 평균과 최악, append의 분할 상환, 공간 복잡도, 그리고 빅오가 알려 주지 않는 것까지 다뤄요.

중급강의 1 / 6약 20분

알고리즘 트랙의 첫 강의예요. 프로그래밍 기초 트랙에서 반복문을 겹치면 횟수가 곱으로 늘어난다고 했고, 수학 기초 트랙의 지수와 로그 강의에서는 빅오 표를 잠깐 봤어요. 이번에는 그 감각을 제대로 다져요. 같은 답을 내는 두 코드가 데이터 1,000개에서는 똑같이 빠르다가, 100만 개에서는 하나는 1초 안에 끝나고 다른 하나는 몇 시간 걸리기도 해요. 이 차이를 코드를 돌려 보기 전에 알아보는 눈이 복잡도예요.

같은 답, 다른 속도

회원 번호 목록에 중복이 있는지 확인하는 방법 세 가지를 짜고, 각각 기본 연산(비교나 확인)을 몇 번 하는지 세어 볼게요.

import random
from functools import cmp_to_key

def dup_pairs(items):                        # 방법 1: 모든 쌍을 비교해요
    steps = 0
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            steps += 1
            if items[i] == items[j]:
                return True, steps
    return False, steps

def dup_sort(items):                         # 방법 2: 정렬한 뒤 이웃끼리만 비교해요
    steps = 0
    def compare(a, b):
        nonlocal steps
        steps += 1
        return (a > b) - (a < b)
    ordered = sorted(items, key=cmp_to_key(compare))
    for a, b in zip(ordered, ordered[1:]):
        steps += 1
        if a == b:
            return True, steps
    return False, steps

def dup_set(items):                          # 방법 3: 본 것을 집합에 기억해요
    steps, seen = 0, set()
    for x in items:
        steps += 1
        if x in seen:
            return True, steps
        seen.add(x)
    return False, steps

random.seed(1)
for n in (1_000, 2_000, 4_000):
    data = random.sample(range(10 * n), n)   # 중복이 없는 경우: 끝까지 다 봐야 해요
    print(f"n={n:>5,}  쌍 비교 {dup_pairs(data)[1]:>9,}번  정렬 {dup_sort(data)[1]:>6,}번  집합 {dup_set(data)[1]:>5,}번")
n=1,000  쌍 비교   499,500번  정렬  9,668번  집합 1,000번
n=2,000  쌍 비교 1,999,000번  정렬 21,286번  집합 2,000번
n=4,000  쌍 비교 7,998,000번  정렬 46,635번  집합 4,000번

셋 다 정답을 내요. 그런데 n이 두 배가 될 때마다 쌍 비교는 4배, 정렬은 2.2배쯤, 집합은 딱 2배로 늘어요(정렬의 비교 횟수는 파이썬 버전에 따라 조금 다를 수 있어요). 실제 시간도 재 볼게요.

import time

def seconds(func, *args, repeat=1):
    start = time.perf_counter()
    for _ in range(repeat):
        func(*args)
    return (time.perf_counter() - start) / repeat

small, big = random.sample(range(10**7), 400), random.sample(range(10**7), 4_000)
t_small, t_big = seconds(dup_pairs, small, repeat=5), seconds(dup_pairs, big)
print("쌍 비교: n이 10배가 되자 시간이 50배 넘게 늘었나요?", t_big / t_small > 50)

per_second = (4_000 * 3_999 / 2) / t_big
million = random.sample(range(10**8), 1_000_000)
estimate = (1_000_000 * 999_999 / 2) / per_second
print("100만 개를 쌍 비교로 검사하면:", "1시간 넘게 걸려요" if estimate > 3600 else "1시간 안에 끝나요")
print("100만 개를 집합으로 검사하면:", "1초 안에 끝나요" if seconds(dup_set, million) < 1 else "1초 넘게 걸려요")
쌍 비교: n이 10배가 되자 시간이 50배 넘게 늘었나요? True
100만 개를 쌍 비교로 검사하면: 1시간 넘게 걸려요
100만 개를 집합으로 검사하면: 1초 안에 끝나요

1,000개일 때는 셋 다 눈 깜짝할 사이에 끝나서 차이를 느낄 수 없어요. 그래서 작은 데이터로 시험할 때는 문제가 보이지 않다가, 서비스가 커진 어느 날 갑자기 느려져요. 쌍 비교로 100만 개를 검사하면 어림잡아 몇 시간이 걸리는데, 집합으로는 1초도 안 걸려요.

시간 대신 횟수를 세요

실행 시간은 컴퓨터의 성능, 언어, 그 순간 함께 돌던 프로그램에 따라 달라져요. 같은 코드를 두 번 재도 결과가 조금씩 달라요. 그래서 알고리즘을 비교할 때는 입력의 크기 n이 커질 때 기본 연산의 횟수가 어떻게 자라는가를 봐요. 이게 시간 복잡도예요. 메모리를 얼마나 더 쓰는지는 공간 복잡도라고 해요.

기본 연산은 비교, 더하기, 값 하나 읽기처럼 한 번에 끝나는 일이에요. 한 번에 걸리는 시간은 컴퓨터마다 다르지만, 몇 번 하는지는 코드만 보고도 셀 수 있어요.

빅오: 가장 빨리 자라는 항만 남겨요

연산 횟수를 정확히 세면 3n² + 5n + 100 같은 식이 나와요. n이 커질 때 각 항이 얼마나 차지하는지 볼게요.

for n in (10, 100, 1_000, 10_000):
    total = 3 * n**2 + 5 * n + 100
    print(f"n={n:>6,}  3n²+5n+100 = {total:>11,}  그중 3n²의 몫 {3 * n**2 / total:.2%}")
n=    10  3n²+5n+100 =         450  그중 3n²의 몫 66.67%
n=   100  3n²+5n+100 =      30,600  그중 3n²의 몫 98.04%
n= 1,000  3n²+5n+100 =   3,005,100  그중 3n²의 몫 99.83%
n=10,000  3n²+5n+100 = 300,050,100  그중 3n²의 몫 99.98%

n이 100만 돼도 3n²이 98%예요. 커질수록 나머지 항은 의미가 없어져요. 그래서 가장 빨리 자라는 항만 남기고, 앞에 곱해진 상수도 버려서 O(n²)이라고 써요. "빅오 n제곱"이라고 읽어요.

상수까지 버리는 이유는, 상수는 컴퓨터와 언어가 바꿀 수 있지만 증가율은 바꾸지 못하기 때문이에요. 연산을 100n번 하는 방법과 n²번 하는 방법을 비교해 볼게요.

print(f"{'n':>7} {'100n':>11} {'n²':>13}  더 적은 쪽")
for n in (10, 50, 100, 1_000, 10_000):
    a, b = 100 * n, n * n
    print(f"{n:>7,} {a:>11,} {b:>13,}  {'n²' if b < a else '100n' if a < b else '같아요'}")
      n        100n            n²  더 적은 쪽
     10       1,000           100  n²
     50       5,000         2,500  n²
    100      10,000        10,000  같아요
  1,000     100,000     1,000,000  100n
 10,000   1,000,000   100,000,000  100n

n이 100보다 작을 때는 n²번 하는 쪽이 오히려 적어요. 하지만 100을 넘으면 100n이 앞서고, 그 차이는 계속 벌어져요. 빅오는 n이 충분히 클 때 누가 이기는지를 알려 줘요. 그래서 상수 100은 빼고 O(n)과 O(n²)으로만 비교해요. 로그의 밑도 같은 이유로 신경 쓰지 않아요. log₂ n과 log₁₀ n은 상수배 차이일 뿐이라(지수와 로그 강의) 그냥 O(log n)이라고 써요.

수학으로 쓰면 이래요. 어떤 양수 cc와 n0n_0가 있어서 n0n_0 이상인 모든 nn에 대해 아래가 성립하면 f(n)=O(g(n))f(n) = O(g(n))이라고 해요.

f(n)≤c⋅g(n)f(n) \le c \cdot g(n)

"충분히 큰 n에서는 g(n)의 상수배를 넘지 않는다", 즉 이보다 빨리 자라지는 않는다는 위쪽 한계예요. 아래쪽 한계는 Ω(오메가), 위아래가 딱 맞는 증가율은 Θ(세타)로 따로 쓰지만, 실무에서는 보통 빅오를 "딱 이만큼 자란다"는 뜻으로 써요.

자주 만나는 복잡도

대표적인 복잡도가 n에 따라 어떻게 자라는지 표로 볼게요. 마지막 칸은 n을 두 배로 늘리면 횟수가 몇 배가 되는지예요.

import math

growth = {
    "O(1)": lambda n: 1,
    "O(log n)": lambda n: math.log2(n),
    "O(n)": lambda n: n,
    "O(n log n)": lambda n: n * math.log2(n),
    "O(n²)": lambda n: n**2,
    "O(2ⁿ)": lambda n: 2**n,
}

def show(v):
    return f"{v:,.0f}" if v < 10**9 else f"{v:.1e}"

print(f"{'':>11}" + "".join(f"{'n=' + str(n):>12}" for n in (10, 20, 40, 80)) + "   n을 2배로")
for name, f in growth.items():
    ratio = "제곱이 돼요" if name == "O(2ⁿ)" else f"{f(2000) / f(1000):.1f}배"
    print(f"{name:>11}" + "".join(f"{show(f(n)):>12}" for n in (10, 20, 40, 80)) + f"   {ratio}")

years = 2**80 / 1e9 / (365.25 * 24 * 3600)
print(f"1초에 10억 번 계산해도 n=80인 O(2ⁿ)은 약 {years / 1e4:,.0f}만 년")
                   n=10        n=20        n=40        n=80   n을 2배로
       O(1)           1           1           1           1   1.0배
   O(log n)           3           4           5           6   1.1배
       O(n)          10          20          40          80   2.0배
 O(n log n)          33          86         213         506   2.2배
      O(n²)         100         400       1,600       6,400   4.0배
      O(2ⁿ)       1,024   1,048,576     1.1e+12     1.2e+24   제곱이 돼요
1초에 10억 번 계산해도 n=80인 O(2ⁿ)은 약 3,831만 년
  • O(1): n과 상관없이 일정해요. 리스트의 i번째 값 읽기, 딕셔너리 조회가 그래요.
  • O(log n): n이 두 배가 돼도 한 번 늘어요. 이진 탐색, 데이터베이스 인덱스.
  • O(n): 한 번 훑기. 합계, 최댓값, 리스트에서 값 찾기.
  • O(n log n): 좋은 정렬 알고리즘. n보다 조금 더 빨리 자라요.
  • O(n²): 모든 쌍 비교. n이 10배가 되면 100배가 돼요.
  • O(2ⁿ): 모든 부분집합 확인. n이 하나 늘 때마다 두 배라, 조합론 강의에서 본 경우의 수 폭발이 여기서 나와요.

마지막 칸은 실제로도 쓸모가 있어요. 코드의 복잡도를 모를 때 n을 두 배씩 늘려 가며 시간을 재고 비율을 보면 돼요. 거의 그대로면 O(1)이나 O(log n), 2배면 O(n), 2배를 조금 넘으면 O(n log n), 4배면 O(n²), 8배면 O(n³)이에요. 이 강의에서는 이걸 두 배 실험이라고 부를게요.

대략의 기준도 알아 두면 좋아요. 파이썬으로 짠 단순한 반복은 1초에 천만 번 단위로 돌아요(컴퓨터마다 달라요). 그러니 n이 100만일 때 O(n log n)인 2,000만 번은 몇 초 안에 끝나지만, O(n²)인 1조 번은 몇 시간에서 하루 가까이 걸려요.

코드에서 복잡도 읽기

돌려 보지 않고 코드만 보고 복잡도를 읽는 규칙은 세 가지예요.

  • 차례로 이어지면 더해요. O(n) 반복 뒤에 O(n) 반복이 또 오면 O(2n), 즉 O(n)이에요. O(n) 뒤에 O(n²)이 오면 큰 쪽만 남아 O(n²)이에요.
  • 안에 들어가면 곱해요. n번 도는 반복 안에서 m번 도는 반복은 O(n·m)이에요.
  • 반씩 줄이면 로그예요. 남은 범위를 매번 반으로 줄이거나, 거꾸로 매번 두 배로 키우면 O(log n)이에요.

네 가지 반복의 횟수를 세어 확인해 볼게요.

def fixed_inner(n):                 # 바깥 n번, 안쪽은 늘 10번
    count = 0
    for i in range(n):
        for j in range(10):
            count += 1
    return count

def halving(n):                     # 남은 범위를 반씩 줄여요
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

def triangle(n):                    # 안쪽이 i번: 0 + 1 + ... + (n - 1)
    count = 0
    for i in range(n):
        for j in range(i):
            count += 1
    return count

def outer_doubling(n):              # 바깥 n번, 안쪽은 1, 2, 4, 8, ...로 키워요
    count = 0
    for i in range(n):
        j = 1
        while j < n:
            j *= 2
            count += 1
    return count

patterns = {
    "안쪽이 늘 10번": fixed_inner,
    "반씩 줄이기": halving,
    "안쪽이 i번": triangle,
    "바깥 n번, 안쪽 2배씩": outer_doubling,
}
for label, f in patterns.items():
    one, two = f(1_024), f(2_048)
    print(f"{label}: n=1,024일 때 {one:,}번, n=2,048일 때 {two:,}번 ({two / one:.2f}배)")
안쪽이 늘 10번: n=1,024일 때 10,240번, n=2,048일 때 20,480번 (2.00배)
반씩 줄이기: n=1,024일 때 10번, n=2,048일 때 11번 (1.10배)
안쪽이 i번: n=1,024일 때 523,776번, n=2,048일 때 2,096,128번 (4.00배)
바깥 n번, 안쪽 2배씩: n=1,024일 때 10,240번, n=2,048일 때 22,528번 (2.20배)
  • 안쪽이 늘 10번이면 n × 10이라 O(n)이에요. 상수 10은 버려요.
  • 반씩 줄이면 n이 두 배가 돼도 한 번만 늘어서 O(log n)이에요.
  • 안쪽이 i번이면 0 + 1 + ... + (n - 1) = n(n - 1)/2번이에요(증명 강의에서 귀납법으로 보인 공식이에요). 가장 빨리 자라는 n²/2가 남아 O(n²)이에요. 안쪽이 평균 절반만 돈다고 덜 나쁜 게 아니에요.
  • 바깥 n번 안에서 두 배씩 키우면 n × log n이라 O(n log n)이에요.

n이 1,024일 때 첫째와 넷째는 횟수가 똑같아요(log₂ 1,024 = 10이니까요). 한 점만 봐서는 구별할 수 없고, n이 커질 때 어떻게 자라는지를 봐야 알 수 있어요.

한 줄에 숨은 반복

반복은 for문에만 있는 게 아니에요. 한 줄짜리 코드가 속에서 반복을 돌기도 해요. 두 회원 목록에서 공통 회원을 찾아볼게요.

members_a = [f"user{i}" for i in range(0, 20_000, 2)]    # 짝수 번호 1만 명
members_b = [f"user{i}" for i in range(0, 20_000, 3)]    # 3의 배수 번호 6,667명

def common_slow(a, b):
    return [x for x in a if x in b]                       # in이 리스트 b를 처음부터 훑어요

def common_fast(a, b):
    b_set = set(b)                                        # 한 번만 집합으로 바꿔 두면
    return [x for x in a if x in b_set]                   # in이 거의 한 번에 끝나요

print("공통 회원:", f"{len(common_fast(members_a, members_b)):,}명")
print("결과가 같나요?", common_slow(members_a, members_b) == common_fast(members_a, members_b))
slow = seconds(common_slow, members_a, members_b)
fast = seconds(common_fast, members_a, members_b, repeat=20)
print("집합으로 바꾸니 100배 넘게 빨라졌나요?", slow / fast > 100)
공통 회원: 3,334명
결과가 같나요? True
집합으로 바꾸니 100배 넘게 빨라졌나요? True

x in b는 한 줄이라 가벼워 보이지만, b가 리스트면 처음부터 하나씩 비교해요. a의 길이를 n, b의 길이를 m이라 하면 common_slow는 O(n·m)이에요. 입력이 둘이면 문자도 둘을 써요. b를 한 번 집합으로 바꿔 두면 바꾸는 데 O(m), 확인 한 번에 평균 O(1)이라 전체가 O(n + m)이 돼요.

파이썬에서 자주 쓰는 연산의 복잡도를 정리하면 이래요.

코드복잡도이유
len(리스트), 리스트[i]O(1)길이를 따로 기억하고, i번째 자리를 바로 계산해요
리스트.append(x), 리스트.pop()O(1)맨 뒤만 건드려요(append는 아래 분할 상환 참고)
x in 리스트, 리스트.index(x)O(n)처음부터 하나씩 비교해요
리스트.remove(x), 리스트.pop(0), 리스트.insert(0, x)O(n)빈칸을 메우거나 자리를 만들려고 뒤의 원소를 모두 옮겨요
리스트[a:b]잘라낸 길이만큼그만큼 새로 복사해요
x in 집합, 딕셔너리[키]평균 O(1)해시로 자리를 바로 계산해요
sorted(리스트), 리스트.sort()O(n log n)비교로 정렬하는 방법 중 가장 빠른 수준이에요(정렬 강의)
min(리스트), sum(리스트)O(n)모두 한 번씩 봐요

데이터베이스 트랙에서 본 N+1 문제도 숨은 반복이에요. 반복문 안에서 질문을 하나씩 보내면, 질문 하나는 빨라도 n번을 보내요. 네트워크를 한 번 오가는 시간이 메모리에서 값 하나를 비교하는 시간보다 수천 배 넘게 길어서, n이 작아도 금방 티가 나요.

반씩 줄이면 로그

정렬된 데이터에서는 가운데를 보고 절반을 버리는 이진 탐색을 쓸 수 있어요. 몇 번 만에 끝나는지 세어 볼게요.

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

for n in (1_000, 1_000_000, 1_000_000_000):
    evens = range(0, 2 * n, 2)                       # 0, 2, 4, ... 정렬된 n개(range는 메모리를 거의 안 써요)
    _, last = binary_search(evens, 2 * (n - 1))      # 맨 끝 값
    _, missing = binary_search(evens, 1)             # 없는 값
    print(f"n={n:>13,}  맨 끝 값 {last:>2}번  없는 값 {missing:>2}번  (log₂ n ≈ {math.log2(n):.1f})")
n=        1,000  맨 끝 값 10번  없는 값 10번  (log₂ n ≈ 10.0)
n=    1,000,000  맨 끝 값 20번  없는 값 20번  (log₂ n ≈ 19.9)
n=1,000,000,000  맨 끝 값 30번  없는 값 30번  (log₂ n ≈ 29.9)

10억 개에서 30번이에요. 하나씩 보면 최악 10억 번인데요. n이 1,000배가 될 때마다 딱 10번씩 늘어요(2¹⁰ = 1,024이니까요). 조건은 하나, 데이터가 정렬돼 있어야 해요. 데이터베이스 인덱스가 빠른 이유도 같아요. B-트리가 정렬된 값을 층층이 나눠 담아 두니, 몇 단계만 내려가면 원하는 값에 닿아요. 파이썬에는 이진 탐색을 해 주는 bisect 모듈도 있어요.

최선, 평균, 최악

리스트에서 값 하나를 찾을 때 첫 칸에 있으면 1번(최선), 없으면 n번(최악), 평균으로는 n/2번쯤 비교해요. 셋이 다를 수 있으니 복잡도를 말할 때는 어느 경우인지가 중요해요.

  • 따로 말이 없으면 보통 최악의 경우를 말해요. 서비스는 언젠가 최악의 입력을 만나고, 공격자는 일부러 최악의 입력을 만들어 보내기도 해요.
  • 평균을 말하는 관례가 있는 것도 있어요. 해시 테이블의 조회는 평균 O(1)이지만 최악은 O(n)이에요(해시 테이블 강의). 퀵 정렬은 평균 O(n log n), 최악 O(n²)이에요(정렬 강의).
  • 맨 처음 예제의 dup_pairs도 중복이 앞쪽에 있으면 금방 끝나요. 그래서 일부러 중복이 없는 최악의 데이터로 쟀어요.

분할 상환: 가끔 비싼 한 번

리스트의 append는 O(1)이라고 했는데, 사실 가끔은 비싸요. 리스트는 원소를 이어진 메모리에 담는데, 빈자리가 다 차면 더 큰 자리를 새로 잡고 원소를 모두 옮겨야 하거든요. 얼마나 자주 그런지 세어 볼게요.

import sys

lst, grows, moved = [], 0, 0
size = sys.getsizeof(lst)
for i in range(1_000_000):
    lst.append(i)
    if sys.getsizeof(lst) != size:          # 빈자리가 모자라 더 큰 자리를 잡은 순간
        grows += 1
        moved += len(lst) - 1               # 그때까지의 원소를 새 자리로 옮겨야 할 수 있어요
        size = sys.getsizeof(lst)
print("append 100만 번 중 자리를 늘린 횟수:", grows)
print("옮긴 원소 수를 모두 더하면 n의 몇 배:", round(moved / len(lst), 1))
append 100만 번 중 자리를 늘린 횟수: 86
옮긴 원소 수를 모두 더하면 n의 몇 배: 8.4

100만 번 중 자리를 늘린 건 86번뿐이에요(정확한 횟수는 파이썬 버전에 따라 다를 수 있어요). 늘릴 때마다 지금 크기에 비례해서 넉넉하게 늘리기 때문이에요. 옮긴 원소를 모두 더해도 n의 8배 남짓이라, 원소 하나당 평균으로는 상수 번이에요. 이렇게 가끔 비싼 일을 전체에 나눠 보면 상수인 경우를 **분할 상환 O(1)**이라고 해요.

반대로 자리가 모자랄 때마다 딱 한 칸씩만 늘린다면 매번 옮겨야 해서, 옮긴 횟수의 합이 1 + 2 + ... + n이 되고 전체가 O(n²)이 돼요. 크기에 비례해 늘리는 게 핵심이에요. 다만 응답 시간이 아주 중요한 곳에서는 이 "가끔 비싼 한 번"이 문제가 되기도 해요.

공간 복잡도

시간만큼 메모리도 따져야 해요. 100만 개의 제곱을 더하는 두 방법이 메모리를 얼마나 쓰는지 재 볼게요.

import tracemalloc

def peak_mb(func):
    tracemalloc.start()
    func()
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    return peak / 1024**2

print(f"리스트에 모아서 더하기: {peak_mb(lambda: sum([i * i for i in range(1_000_000)])):.0f}MB")
print(f"하나씩 만들며 더하기: {peak_mb(lambda: sum(i * i for i in range(1_000_000))):.2f}MB")
리스트에 모아서 더하기: 39MB
하나씩 만들며 더하기: 0.00MB

리스트에 다 모았다가 더하면 100만 개를 한꺼번에 들고 있어야 해서 O(n)의 메모리를 써요. 대괄호를 뺀 제너레이터는 하나씩 만들어 더하고 버리니 O(1)이에요. 시간은 둘 다 O(n)인데 메모리가 달라요.

맨 처음의 집합 방식도 공짜가 아니에요. 본 값을 모두 기억하느라 메모리를 O(n) 더 써요. 메모리를 내주고 시간을 사는 거래예요. 서버 트랙에서 본 캐시도 같은 거래고요. 데이터가 메모리에 다 들어가지 않을 만큼 크면 이 거래를 할 수 없으니, 데이터를 나눠서 처리하거나 디스크를 잘 다루는 데이터베이스에 맡겨요. 재귀 호출도 부를 때마다 메모리를 쓰는데, 이건 재귀와 동적 계획법 강의에서 다뤄요.

빅오가 알려 주지 않는 것

  • 작은 n에서는 상수가 이겨요. 위의 100n과 n² 비교처럼요. 파이썬의 정렬도 짧은 구간은 단순한 삽입 정렬로 처리해요. n이 작으면 그게 더 빠르거든요.
  • 메모리를 읽는 순서도 속도를 바꿔요. 같은 O(n)이라도 메모리를 차례로 읽으면 빠르고, 여기저기 건너뛰며 읽으면 느려요. 컴퓨터 과학 심화 트랙의 컴퓨터 구조 강의에서 다루는 캐시 이야기예요.
  • 느린 원인은 알고리즘 밖에 있을 때가 많아요. 실제 서비스가 느린 이유는 데이터베이스 질문, 네트워크, 디스크인 경우가 많아요.

그래서 순서가 중요해요. 먼저 재고, 가장 오래 걸리는 곳을 찾은 다음, 그 부분의 복잡도를 따져서 고치고, 다시 재요. 파이썬에서는 python -m cProfile -s cumtime 내프로그램.py로 함수마다 걸린 시간을 볼 수 있어요. 재 보지 않고 짐작으로 고치면 엉뚱한 곳을 손보기 쉬워요.

실습

  1. sorted()로 10만, 20만, 40만 개의 무작위 수를 정렬하는 시간을 seconds로 재고 비율을 보세요. 2배를 조금 넘나요?
  2. 빈 리스트에 insert(0, x)로 1만, 2만, 4만 개를 넣는 시간을 재 보세요. 몇 배씩 늘어나나요? 표를 보고 이유를 설명해 보세요.
  3. 세 목록에 모두 있는 회원을 찾는 함수를 O(n²) 없이 만들어 보세요.
  4. dup_pairs에서 중복이 맨 앞 두 칸에 있으면 몇 번 만에 끝나나요? 최선과 최악의 경우를 n으로 말해 보세요.
  5. 분할 상환 실험에서 자리가 모자랄 때마다 한 칸씩만 늘린다면, 옮긴 원소 수의 합이 얼마일지 n = 100만으로 계산해 보세요.

자주 하는 실수

  • 작은 데이터로만 시험한다. 1,000개에서 빠르다고 100만 개에서도 빠른 건 아니에요. 실제 크기나 그 10배로 재 봐요.
  • 한 줄에 숨은 반복을 못 본다. 반복문 안의 in 리스트, remove, pop(0), 데이터베이스 질문을 먼저 의심해요.
  • 빅오를 실행 시간으로 착각한다. O(n)이 O(n²)보다 언제나 빠른 게 아니라, n이 충분히 크면 이길 뿐이에요.
  • 재 보지 않고 고친다. 짐작한 곳은 병목이 아닐 때가 많아요.
  • 평균과 최악을 섞는다. 평균 O(1)인 구조도 최악은 다를 수 있어요.
  • 메모리를 잊는다. 시간을 아끼려다 메모리가 바닥나면 프로그램이 멈춰요.

점검 문제

  1. 알고리즘을 비교할 때 실행 시간보다 연산 횟수의 증가율을 보는 이유는?
  2. 연산 횟수가 5n² + 300n + 2,000인 코드의 복잡도를 빅오로 쓰고, 그렇게 줄이는 이유를 말해 보세요.
  3. n을 두 배로 늘렸더니 시간이 약 4배가 됐어요. 복잡도를 어떻게 짐작할 수 있나요?
  4. 정렬된 10억 개에서 이진 탐색은 최대 몇 번쯤 비교하나요? 정렬돼 있지 않다면요?
  5. for x in a: 안에서 if x in b:를 쓰는 코드(a의 길이는 n, b는 길이 m인 리스트)의 복잡도와 고치는 법은?
  6. append가 가끔 오래 걸리는데도 O(1)이라고 하는 이유는?
  7. 집합으로 중복을 검사하는 방법이 아끼는 것과 대신 쓰는 것은?
  8. O(n²)인 방법이 O(n log n)인 방법보다 빠를 수 있는 경우는?

정답

  1. 실행 시간은 컴퓨터, 언어, 그때의 상황에 따라 달라지지만, 입력이 커질 때 연산 횟수가 자라는 모양은 코드가 정하기 때문이에요. 그래서 데이터가 커졌을 때 어떻게 될지 미리 알 수 있어요.
  2. O(n²)이에요. n이 커지면 5n²이 거의 전부를 차지하고, 앞의 상수 5는 컴퓨터나 언어에 따라 달라지는 값이라 증가율을 비교하는 데는 의미가 없어요.
  3. 두 배에 4배면 n²에 비례해 자란다는 뜻이라 O(n²)일 가능성이 커요. n을 몇 번 더 두 배로 늘려서 비율이 계속 4배 근처인지 확인해요.
  4. log₂ 10억이 약 30이라 30번쯤이에요. 정렬돼 있지 않으면 하나씩 봐야 해서 최악 10억 번이에요.
  5. a를 돌 때마다 b를 처음부터 훑으니 O(n·m)이에요. 반복 전에 b를 한 번 집합으로 바꾸면 O(n + m)이 돼요.
  6. 자리를 늘릴 때 크기에 비례해 넉넉하게 늘려서 비싼 옮기기는 드물게 일어나고, 전체에 나누면 원소 하나당 상수 번이기 때문이에요. 이걸 분할 상환 O(1)이라고 해요.
  7. 시간을 O(n²)에서 O(n)으로 아끼는 대신, 본 값을 모두 기억하느라 메모리를 O(n) 더 써요.
  8. n이 작을 때예요. 빅오가 버린 상수가 작은 n에서는 결과를 바꿀 수 있어요. 그래서 파이썬의 정렬도 짧은 구간은 삽입 정렬로 처리해요.

다음 강의

오늘 표에서 pop(0)과 insert(0, x)는 O(n)이고, append와 pop()은 O(1)이었어요. 같은 리스트인데 왜 앞과 뒤가 다를까요? 다음 강의에서는 데이터를 메모리에 늘어놓는 기본 방식인 배열과 연결 리스트, 그리고 그 위에 만든 스택과 큐를 다루면서 이 차이를 속부터 이해해요.