Jun's note

이 분석은 “최악”의 경우에 대한 것이다. Amortized Analysis 정의 “최악의 경우에 대해 최악의 경우가 발생하도록 연속된 연산을 수행하고, 그때 한 번의 연산에 대한 평균수행시간을 분석하는 것” 이것이 왜 필요한가? 예를 들어, 비용을 1만큼 쓰는 연산이 있는데 이 연산은 가끔 n번 발생한다고 하면, Asymptotic analysis(점근적 분석)을 사용하면 이 연산은 O(n)이 된다. 하지만 가끔 일어나는 경우 때문에 O(n)이라고 하기에는 아깝다. 이를 보완하기 위해 나온 분석이 “Amortized Analysis”이다 다시 말하면 Amortized Analysis는 최악의 경우에 연속으로 발생하는 연산의 “평균비용”을 의미한다. (Array Doubling) n크기의 배열이 꽉 차 ..