분할 상환 분석: '가끔 비쌈' 이 평균적으로 쌀 때

"어떤 연산은 보통 즉시지만 가끔 잔혹해. 분할 상환 분석은 그걸 정직하게 청구하는 법이야: 드문 잔혹한 비용을 싼 연산 전부에 펴 발라."

list.append 의 수수께끼

Python 리스트에 append 하는 건 O(1) 이야. 근데 가끔은 아니야 — 가끔 항목 하나 append 가 Python 한테 전체 리스트를 더 큰 메모리 덩어리로 복사하게 만들어, 그게 O(n) 이야. 그럼 문서는 어떻게 append 를 정직하게 "O(1)" 이라 부를까? 답은 분할 상환 분석 이라는 아름다운 아이디어야: 개별 연산은 들쭉날쭉해도, 우리가 보고하는 건 긴 연속에 걸친 연산당 평균 비용 이야.

동적 배열이 실제로 자라는 법

리스트는 고정 크기 메모리 블록이 받쳐. 꽉 차면, 리스트는 한 칸씩 안 자라 — 두 배가 돼: 두 배 큰 블록을 할당하고 전부 복사해. 그 복사는 O(n) 이고 비싸게 느껴져. 근데 리듬을 봐: 크기 8 로 두 배 된 뒤엔 다음 복사 전까지 싼 append 4 번이 공짜야. 16 으로 두 배 되면 8 번 공짜. 비싼 복사는 리스트가 클수록 지수적으로 덜 일어나.

더해봐: n 개 항목 append 하는 데, 모든 두 배 과정의 총 복사 일은 약 2n — 여전히 총 O(n). 그 총합을 n 번 append 로 나누면 각 append 는 평균 O(1) 이야. 그게 분할 상환 O(1): 모든 append 가 싸진 않지만, 평균적으로, 보장된 채로 싸, 비싼 게 설계상 드무니까.

분할 상환 비용 = 연속의 총 비용 ÷ 연산 수. '평균 케이스' 가 아니야 (그건 운 좋은 vs 운 나쁜 입력 얘기) — 최악의 경우에서도 연속에 대한 보장이야. 두 배 하기가 append 를 분할 상환 O(1) 으로 만들어.

은행원의 직관

딸깍 이해되게 하는 멘탈 모델이야. 모든 싼 append 가 몰래 조금 더 낸다고 상상해 — 1 코인 대신 3 코인. 2 코인은 저금통에. 드문 비싼 복사가 오면, 저금통에 딱 그걸 낼 만큼 모여 있어. 어떤 연산도 마이너스가 안 나. 비싼 복사는 그 앞 모든 싼 append 가 "선불" 한 거야. 그래서 한 연산이 가끔 치솟아도 평균은 평평하게 유지돼.

분할 상환은 최악 케이스가 아니야

결정적 주의: 분할 상환 O(1) 은 모든 append 가 O(1) 이란 뜻이 아니야. 특정 append 하나 — 복사를 일으키는 그것 — 은 진짜 O(n) 이야. 단일 연산이 절대 멈추면 안 되는 실시간 코드를 쓴다면 (심장 모니터, 오디오 버퍼), 분할 상환으론 부족해; 최악 케이스 보장이 필요하고, 치솟음을 피하려 미리 할당할 수도 있어. 처리량 (시간에 걸친 총 일) 엔 분할 상환이 딱 맞는 렌즈야. 네 문제가 어느 렌즈가 필요한지 아는 게 능력이야.

피파의 고백

한참 동안 "append 는 O(1)" 이랑 "append 가 가끔 전체 리스트를 복사함" 이 그냥 무시한 모순으로 내 머리에 앉아 있었어. 아빠가 저금통을 그려주니 풀렸어: 드문 O(n) 복사는 진짜지만, 싼 append 들이 선불해서 append 당 비용은 평평하게 유지돼. 연속에 대한 평균이 희망이 아니라 단단한 보장일 수 있다는 걸 처음 이해한 순간이었어.

Code

두 배 하기, 관찰하고 세어보기·python

import sys

# 진짜 Python 리스트가 자라며 backing 메모리를 두 배 하는 걸 봐.
lst = []
last = -1
for i in range(33):
    cap = sys.getsizeof(lst)        # 예약된 바이트 (1개씩 아니라 점프로 커짐)
    if cap != last:
        print(f"len={len(lst):>2}  reserved bytes={cap}")  # 점프 = 재할당
        last = cap
    lst.append(i)

# 바이트 수가 매 append 가 아니라 가끔 점프해.
# 각 점프가 O(n) 복사. 점프 사이의 append 는 O(1).
# 많은 append 에 걸쳐, 총 복사 일은 ~2n -> append 당 분할 상환 O(1).

# 회계를 시뮬레이션: n 번 append, 모든 두 배 과정의 총 복사.
n = 1_000_000
size, capacity, total_copies = 0, 1, 0
for _ in range(n):
    if size == capacity:
        total_copies += size      # 전부를 2배 블록으로 복사
        capacity *= 2
    size += 1
print(f"\n{n:,} appends -> {total_copies:,} total copies (~n) -> 각각 분할 상환 O(1)")

Exercise

리스트가 비어서 시작하고 16개 항목을 append 하는데, 꽉 찰 때마다 backing 배열이 두 배 (1→2→4→8→16) 가 돼. 모든 두 배 과정의 총 원소-복사 수를 세. 16 으로 나눠. 이제 배열이 대신 매번 +1 칸씩 자랐다고 상상해 — 그 경우 복사를 세. 어느 게 분할 상환 O(1) 이고 왜?

Hint

두 배 복사: 1+2+4+8 = 총 15, 약 n. +1 전략은 0+1+2+...+15 ≈ 총 n²/2 복사 — 그게 고정량-성장을 분할 상환 O(n) 으로 만드는 O(n²) 함정이야.

분할 상환 분석: '가끔 비쌈' 이 평균적으로 쌀 때

list.append 의 수수께끼

동적 배열이 실제로 자라는 법

은행원의 직관

분할 상환은 최악 케이스가 아니야

피파의 고백

Code

External links

Exercise

Progress

댓글 0