"어떤 연산은 대개 즉시인데 가끔 잔혹해. 분할 상환 분석은 그걸 정직하게 청구하는 방법이야. 드물게 오는 잔혹한 비용을 싼 연산 전체에 펴 바르는 거지."
list.append의 수수께끼
파이썬 리스트에 append 하는 건 O(1)이야. 그런데 가끔은 아니야. 항목 하나를 append 했을 뿐인데 파이썬이 리스트 전체를 더 큰 메모리 덩어리로 복사하는 일이 생기고, 그건 O(n)이거든. 그럼 문서는 무슨 낯으로 append를 "O(1)"이라고 부를까? 답이 분할 상환 분석이라는 아름다운 아이디어야. 개별 연산은 들쭉날쭉해도, 우리가 보고하는 건 긴 연속에 걸친 연산당 평균 비용이라는 것.
동적 배열이 실제로 자라는 법
리스트는 현재 길이보다 여유 있는 메모리 블록을 잡아둬. 여유가 모자라면 더 큰 블록을 마련하고 기존 참조를 옮기는데, 이 한 번의 재할당이 O(n)이야. 중요한 건 정확히 두 배가 된다는 규칙이 아니라 여유 공간을 두고 기하급수적으로 키우는 전략이라는 점이야. CPython의 실제 증가 폭은 버전에 따라 달라질 수 있지만, 재할당 사이에 값싼 append가 충분히 많이 끼도록 설계돼 있어.
이해를 돕는 모델로 용량이 두 배씩 커진다고 그려보자. 8칸으로 커진 뒤엔 다음 재할당까지 싼 append가 최대 4번, 16칸이면 8번 따라와. 옮긴 원소 수도 1+2+4+…이라 n개를 넣을 때 2n보다 작아. 그래서 총 복사량은 O(n)이고 append당 분할 상환 비용은 O(1)이야. 이건 분석하기 쉬운 모델이지 CPython이 정확히 두 배로 큰다는 약속은 아니야. 핵심은 고정된 칸을 더하는 게 아니라 일정한 배수로 키워서 비싼 복사 사이에 값싼 append를 많이 끼워 넣는다는 거야.
은행원의 직관
단번에 이해되게 하는 멘탈 모델이 있어. 싼 append가 저마다 몰래 조금씩 더 낸다고 상상해봐. 1코인 대신 3코인. 2코인은 저금통에 넣고. 드물게 비싼 복사가 닥치면 저금통에 딱 그걸 낼 만큼 모여 있어. 어떤 연산도 마이너스가 안 나. 비싼 복사는 그 앞의 싼 append들이 미리 낸 셈이거든. 그래서 한 연산이 가끔 치솟아도 평균은 평평하게 유지돼.
분할 상환은 최악 케이스가 아니야
결정적인 주의사항. 분할 상환 O(1)은 모든 append가 O(1)이라는 뜻이 아니야. 복사를 일으키는 그 한 번의 append는 진짜 O(n)이야. 단일 연산이 절대 멈추면 안 되는 실시간 코드를 쓴다면 (심장 모니터, 오디오 버퍼) 분할 상환으로는 부족해. 최악 케이스 보장이 필요하고, 치솟음을 피하려고 미리 할당할 수도 있어. 반면 처리량이 문제라면, 즉 시간에 걸친 총 일이 관심사라면 분할 상환이 딱 맞는 렌즈야. 내 문제가 어느 렌즈를 요구하는지 아는 게 진짜 실력이고.