부산대학교자료구조
Scientific Inference Lab

When the Array Fills Up

Amortized Cost

늘리는 규칙에 따라 재할당 간격과 누적 복사량이 달라진다. 연속한 추가의 쓰기와 복사를 모두 더한 뒤 호출 수로 나누어 한 번당 비용을 구한다.

누적 복사재할당이 일어날 때 기존 원소를 옮긴 횟수를 모두 더한다.
상각 비용(amortized cost)어떤 순서로 m번 호출해도 총비용이 m×c를 넘지 않게 하는 한 번당 비용의 상한 c다.
평균 경우와의 차이상각 비용은 입력 분포를 가정하지 않고, 평균 경우(average case)는 입력의 확률 분포로 기대 비용을 구한다.

쓰기와 복사를 더한 총비용을 호출 수로 나누면 한 번당 비용이 된다

늘리는 규칙과 호출 수 m을 바꾸면 호출마다의 비용 막대와 총비용, 한 번당 비용이 함께 바뀐다.

막대 하나가 호출 한 번의 비용(쓰기 1회와 그 호출의 복사)이다. 초록 윗선 막대는 재할당이 일어난 호출이다.

두 배로 늘리면 한 번당 비용이 3 아래에 머문다

위 막대와 별도로 호출 수 m을 정해 두 규칙의 총비용과 한 번당 비용을 비교한다.

두 카드는 같은 m에서 쓰기·복사·총비용과 한 번당 비용이다.