분할 상환 비용

분할 상환 비용은 가끔 크게 비싸지는 연산이 한 번에 얼마꼴을 치르는지 알려 줍니다. 칸이 차면 늘어나는 배열에 값을 넣는 일이 그런 연산입니다. 드물게 드는 큰 비용을 앞뒤의 싼 연산들에 나눠 얹어서 셉니다. 이렇게 센 몫은 가끔 오래 걸리는 연산에서도 작게 나옵니다.

쉽고 빠른 이해

분할 상환 비용은 연산을 여러 번 했을 때 한 번에 돌아가는 몫입니다. 크기가 늘어나는 배열에 값을 넣는 일이 대표적입니다. 대부분은 빈 칸에 값 하나를 쓰면 끝납니다. 칸이 다 찼을 때만 더 큰 공간으로 값을 전부 옮깁니다.

이렇게 나눠 세지 않으면 가장 비싼 한 번을 기준으로 전부를 셀 수밖에 없습니다. 그러면 값 넣기 한 번이 데이터 크기만큼 걸린다고 말해야 합니다. 값을 쭉 넣어 보면 그보다 훨씬 적게 듭니다.

이렇게 셉니다.

1. 연산을 여러 번 이어서 한다
2. 그동안 든 비용을 모두 더한다
3. 더한 합을 연산 횟수로 나눈다

분할 상환 비용은 한 번 한 번이 늘 짧게 끝난다는 약속이 아닙니다. 비싼 한 번에 걸린 요청은 그 순간 눈에 띄게 늦어집니다.

상세

해마다 한 번 120만 원을 내는 보험이 있다고 해 봅시다. 보험료를 내는 달에는 큰돈이 나갑니다. 나머지 열한 달에는 한 푼도 안 나갑니다. 그래도 가계부에는 한 달에 10만 원씩 나간다고 적어 두는 편이 씀씀이를 가늠하기 쉽습니다.

분할 상환 비용은 이 계산을 연산에 옮긴 것입니다. 연산을 여러 번 이어서 했을 때 든 비용을 모두 더합니다. 그 합을 연산 횟수로 나누면 한 번당 몫이 나옵니다. 이 몫이 분할 상환 비용입니다.

이름의 「분할 상환」은 빚을 여러 번에 나눠 갚는다는 금융 용어에서 왔습니다. 영어로는 amortized cost 라고 합니다.

이 몫이 필요한 까닭은 비싼 연산이 드물게만 오는 자료구조가 많기 때문입니다. 비싼 한 번을 모든 연산의 비용으로 치면 실제보다 훨씬 많이 든다는 답이 나옵니다. 분할 상환 비용은 그 한 번을 싼 연산들 사이에 나눠 얹습니다. 그러면 여러 번 이어 쓸 때 드는 비용에 맞는 답이 나옵니다.

아래에서는 크기가 늘어나는 배열 하나에 값을 여러 번 넣으며 비용을 셉니다. 그 계산으로 한 번당 몫이 왜 일정하게 남는지 봅니다. 그다음 평균의 경우와 무엇이 다른지 가릅니다. 마지막으로 이 몫이 감추는 한 번의 멈춤을 봅니다.

칸이 차면 늘어나는 배열

배열은 정해진 개수의 칸을 메모리에 나란히 잡아 두고 씁니다. 칸 수를 처음에 정하므로 칸이 다 차면 값을 더 넣을 수 없습니다. 몇 개를 넣을지 미리 모르는 경우가 많아서 이것만으로는 불편합니다.

동적 배열은 칸이 다 차면 스스로 칸을 늘리는 배열입니다. 더 큰 칸을 새로 잡습니다. 있던 값을 전부 새 칸으로 옮긴 뒤 옛 칸을 버립니다. 파이썬의 list 와 자바의 ArrayList 가 동적 배열입니다.

값을 넣는 일은 두 가지로 갈립니다. 빈 칸이 남아 있으면 값 하나를 쓰면 끝납니다. 칸이 다 찼으면 먼저 들어 있던 값을 모두 옮긴 뒤에 새 값을 씁니다. 이때는 들어 있는 값의 수만큼 일이 늘어납니다.

칸을 얼마나 늘리는지는 구현마다 다릅니다. 여기서는 계산이 쉬운 두 배로 봅니다. 칸 하나에서 시작해 1, 2, 4, 8 칸으로 늘어납니다.

비싼 한 번으로 전부를 세면

값 넣기 한 번은 운이 나쁘면 들어 있던 값 n 개를 옮겨야 합니다. 여기서 n 은 배열에 든 값의 수입니다. 이렇게 가장 비싼 한 번을 기준으로 삼아 세는 방식을 최악의 경우 분석이라고 합니다.

빅오 표기법은 입력이 커질 때 할 일이 어떤 꼴로 늘어나는지를 적는 방법입니다. 정확히 몇 번 걸리는지 세지 않아도 늘어나는 꼴만으로 비용을 견줄 수 있습니다.

최악의 경우를 기준으로 삼으면 n 번 넣는 데 n × n 만큼 든다는 답이 나옵니다. 이것을 빅오 표기법으로 O(n²) 이라고 적습니다. O(n²) 은 입력이 두 배가 되면 일이 네 배가 되는 꼴입니다.

그런데 옮기기는 매번 일어나지 않습니다. 칸을 두 배로 늘리고 나면 한동안은 빈 칸이 넉넉합니다. 비싼 한 번 다음에는 싼 넣기가 여러 번 이어집니다. 그래서 O(n²) 은 한참 부풀린 답입니다.

여덟 번 넣으며 세기

칸 하나짜리 빈 배열에 값을 여덟 번 넣어 봅니다. 값 하나를 쓰는 일과 값 하나를 옮기는 일을 각각 비용 1 로 칩니다. 아래 표는 넣기마다 옮긴 값의 수와 그 넣기의 비용입니다.

여덟 번에 든 비용을 모두 더하면 15 입니다. 쓰기가 8 입니다. 옮기기는 1 + 2 + 4 = 7 입니다. 15 를 8 로 나누면 한 번에 2 가 채 안 됩니다.

옮기기의 합이 작게 남는 까닭은 옮기는 수가 두 배씩 커지기 때문입니다. 1, 2, 4, 8 처럼 두 배씩 커지는 수를 모두 더하면 합은 언제나 마지막 수의 두 배보다 작습니다. 마지막으로 옮긴 값의 수는 넣은 횟수 n 보다 작습니다. 그래서 옮기기는 모두 합쳐도 2n 을 넘지 않습니다.

쓰기 n 번에 옮기기 2n 번 미만을 더하면 전체는 3n 을 넘지 않습니다. 넣기 한 번의 분할 상환 비용은 3 이하입니다. n 이 아무리 커져도 이 상한은 안 변하므로 O(1) 이라고 적습니다. O(1) 은 입력이 커져도 한 번에 드는 일이 늘지 않는다는 뜻입니다.

아래 그림은 넣기를 열여섯 번까지 이어 간 것입니다. 막대 하나는 넣기 한 번의 비용입니다. 선은 첫 넣기부터 그 넣기까지의 비용을 더해 횟수로 나눈 몫입니다. 막대는 2, 3, 5, 9 로 점점 높이 솟습니다. 선은 3 아래에서 크게 움직이지 않습니다.

xychart-beta
    title "넣기마다의 비용과 한 번당 몫"
    x-axis "넣기 순번" [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
    y-axis "비용" 0 --> 10
    bar [1, 2, 3, 1, 5, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 1]
    line [1, 1.5, 2, 1.8, 2.4, 2.2, 2, 1.9, 2.7, 2.5, 2.4, 2.3, 2.2, 2.1, 2, 1.9]

미리 떼어 두고 세기

같은 결과를 다른 눈으로 볼 수도 있습니다. 넣기마다 비용 3 을 낸다고 치는 것입니다. 1 은 자기 값을 쓰는 데 씁니다. 나머지 2 는 나중에 올 옮기기에 대비해 떼어 둡니다.

칸이 4 칸에서 8 칸으로 늘 때 옮길 값은 네 개입니다. 직전에 칸을 늘린 뒤로 들어온 값은 셋째와 넷째, 두 개입니다. 첫째와 둘째가 떼어 둔 몫은 앞서 1 칸을 2 칸으로, 2 칸을 4 칸으로 늘릴 때 옮기는 데 이미 썼습니다.

그래서 이번에는 새로 들어온 둘이 옛 값까지 옮겨 줍니다. 둘이 2 씩 떼어 둔 4 로 값 네 개를 옮깁니다.

칸이 8 칸에서 16 칸으로 늘 때도 같습니다. 그사이 들어온 값 네 개가 떼어 둔 8 로 값 여덟 개를 옮깁니다. 떼어 둔 몫이 모자란 적이 없으니 넣기 한 번에 3 이면 늘 충분합니다.

이런 몫을 구하는 방법을 통틀어 분할 상환 분석이라고 부릅니다. 앞 소절처럼 모두 더해 나누는 방법이 집계 방법입니다. 이 소절처럼 연산마다 떼어 두는 방법은 회계 방법입니다.

셋째 방법인 잠재 함수 방법은 쌓아 둔 몫을 자료구조 전체에 하나로 셉니다. 이 배열이라면 칸이 찰수록 그 몫이 커집니다. 칸을 늘려 값을 옮기면 그 몫이 줄어듭니다. 줄어든 만큼이 옮기기 비용을 치릅니다.

평균의 경우와 다른 점

평균의 경우 분석도 「평균」이라는 말을 씁니다. 하지만 무엇을 두고 평균을 내는지가 다릅니다. 평균의 경우는 먼저 입력이 어떻게 들어올지 가정합니다. 그 가정 아래에서 한 번에 드는 비용을 평균 냅니다.

분할 상환 비용에는 그런 가정이 없습니다. 어떤 값을 어떤 순서로 넣든 여덟 번 넣는 비용은 15 입니다. 어떤 입력이 와도 n 번에 3n 을 넘지 않습니다. 운에 기대지 않는 보장입니다.

해시테이블이 둘을 함께 보여 줍니다. 해시테이블은 키마다 들어갈 칸을 계산해 값을 넣습니다. 키로 찾는 일이 평균 O(1) 인 것은 키가 칸에 고르게 흩어진다고 가정했을 때입니다. 이쪽은 평균의 경우입니다.

해시테이블도 칸이 차면 칸 수를 늘립니다. 그리고 키를 새 칸에 다시 나눠 담습니다. 이 일을 리해싱이라고 합니다. 가끔 비싼 리해싱을 넣기 여러 번에 나눠 세는 쪽은 분할 상환 비용입니다.

칸을 늘리는 폭과 빈 칸

칸을 두 배로 늘리면 늘린 직후에는 절반 가까이가 비어 있습니다. 값이 n 개일 때 칸은 2n 개에 가깝게 잡혀 있을 수 있습니다. 옮기기를 드물게 만든 대가를 메모리로 치른 것입니다. 메모리가 입력에 따라 얼마나 느는지 재는 잣대가 공간 복잡도입니다.

늘리는 비율을 크게 잡으면 옮기기는 더 드물어집니다. 대신 빈 칸이 더 많아집니다. 비율을 작게 잡으면 그 반대입니다.

칸을 비율이 아니라 일정한 개수씩 늘리면 한 번당 몫이 일정하게 남지 않습니다. 늘 열 칸씩 늘린다면 열 번 넣을 때마다 들어 있는 값을 전부 옮깁니다.

옮기는 수는 10, 20, 30 … 처럼 n 까지 늘어납니다. 이런 수를 모두 더하면 합이 n² 에 비례합니다. 한 번당 몫이 n 에 비례해 커지므로 O(1) 이 아니라 O(n) 입니다.

한 번의 멈춤은 남는다

분할 상환 비용은 여러 번을 합친 몫입니다. 한 번 한 번이 짧게 끝난다는 약속은 아닙니다. 값이 백만 개 든 배열이 칸을 늘리는 그 한 번은 값 백만 개를 옮깁니다.

요청이 올 때마다 값을 동적 배열에 하나씩 넣는 서버라면 이 한 번이 응답 시간에 드러납니다. 요청 대부분은 값 하나를 쓰고 끝납니다. 값이 백만 개 찬 뒤 칸을 늘리게 된 요청 하나만 값 백만 개를 옮기느라 눈에 띄게 늦어집니다.

응답이 가장 늦은 쪽 끝에 몰린 요청들의 지연을 꼬리 지연이라고 부릅니다. 드문 멈춤은 평균 응답 시간에는 묻힙니다. 꼬리 지연을 보면 드러납니다.

이 멈춤을 줄이는 흔한 방법이 둘 있습니다. 넣을 개수를 미리 알면 처음부터 칸을 넉넉히 잡아 둡니다. 그러면 칸을 늘릴 일이 아예 생기지 않습니다. 자바의 ArrayList 는 만들 때 처음 칸 수를 받습니다(new ArrayList<>(1000)).

미리 알 수 없으면 옮기기를 여러 번에 조금씩 나눠 할 수 있습니다. 옛 칸과 새 칸을 한동안 같이 둡니다. 넣기가 올 때마다 몇 개씩만 옮깁니다. 해시테이블에서 이렇게 하는 것을 점진적 리해싱이라고 부릅니다.

관련 항목

분할 상환 비용을 구하는 분석 방법

분할 상환 분석 · 집계 방법 · 회계 방법 · 잠재 함수 방법

분할 상환 비용과 견주는 분석 기준

최악의 경우 · 평균의 경우 · 최선의 경우 · 평균

분할 상환 비용을 적는 복잡도 잣대

시간 복잡도 · 공간 복잡도 · 빅오 표기법 · 점근 분석 · 복잡도 · 알고리즘

분할 상환 비용으로 성능을 말하는 자료구조와 연산

동적 배열 · 배열 · 해시테이블 · 리해싱 · 스택 · 스플레이 트리 · 서로소 집합 · 피보나치 힙 · 자료구조

한 번의 긴 멈춤을 줄이는 기법

점진적 리해싱 · 증분 가비지 컬렉션 · 사전 할당

분할 상환 비용에 묻히는 지연을 재는 지표

응답 시간 · 꼬리 지연 · 백분위수 · 지연