Amortized Analysis

Amortized Runtime Analysis: 분할 상환 런타임 분석

 

알고리즘 A는 아래와 같은 규칙적인 런타임 패턴을 보인다고 하자.

• 각 루프에서는 $\Theta(1)$의 시간이 걸린다.
• 마지막 루프에서는 $\Theta(n)$의 시간이 걸린다.

그렇다면 알고리즘 A의 전체 런타임은 얼마일까? $\Theta(n)$이다.

마지막 루프에서 발생하는 시간 $\Theta(n)$이 이전 모든 루프에 고르게 분배된다고 가정하면, 각 루프의 평균적인 시간은 여전히 $\Theta(n)$이 된다. 이러한 방식의 런타임 분석을 분할 상환 분석이라 부른다.

 

하지만, 알고리즘 B는 알고리즘 A와 다소 다르다.

• 대부분의 루프는 $\Theta(1)$의 시간이 걸린다.
• 가끔 드물게 $\Theta(n)$의 시간이 걸리는 루프가 발생한다.

이처럼 불규칙적인 패턴을 가지고 있는 알고리즘 B의 경우, 최악의 경우 런타임 분석을 적용하여 런타임을 결정한다.

---

동적 배열에서의 숫자를 저장하는 프로그램의 평균 실행 시간을 분석해보자.

동적 배열은 크기가 부족할 경우 크기를 확장하며, 확장이 발생할 때 기존 배열의 모든 값을 새 배열로 복사해야한다.

 

일반적인 경우, 배열에 값을 추가하는 작업은 $\Theta(1)$이다. 이는 단순히 배열의 다음 위치에 값을 삽입하는 작업이다.

확장이 발생할 경우, 새로운 배열의 크기는 기존 배열의 두 배가 된다. 기존 배열의 모든 값(n개)을 새 배열로 복사해야하므로, 이 경우 $\Theta(n)$의 시간이 걸린다. 

 

배열이 확장되는 시간마다 $\Theta(n)$의 작업이 발생하지만, 확장은 상대적으로 드물게 발생한다.

각 삽입 작업을 기준으로 평균 실행 시간을 계산하면, 모든 확장 비용이 분산되므로 삽입 작업의 평균 시간은 여전히 $\Theta(1)$로 유지된다. 

$\frac{n\Theta(1)+\Theta(n)}{n+1} = \Theta(1)$

 

이처럼, 드물게 발생하는 큰 비용이 모든 작업에 고르게 분배되는 경우를 분석하는 기법이 분할 상환 분석이다.

---

Worst case, Average case, and Amortized complexity

 

최악의 경우 실행시간은 알고리즘이 입력 사례 중 가장 나쁜 경우에 대해 보여주는 성능이다.

최악의 경우 실행시간은 어떤 입력에 대해서도 실행 시간이 이를 초과하지 않는다는 상한선(upper bound)을 제공한다.

이는 알고리즘이 절대 이 시간 이상 걸리지 않을 것을 보장하며, 실행 시간을 예측하기 위해 추가적인 추측이 필요하지 않다.

 

평균 실행 시간은 알고리즘이 랜덤하게 주어진 입력에 대해 보여주는 예상 성능이다.

평균 실행 시간은 '평균적인 입력'에 대한 실행 시간의 추정치인 것이다.

이를 계산하려면,

• 가능한 모든 입력 사례를 알고 있어야 하며,
• 각 사례가 발생할 확률 분포를 알아야 하고,
• 각 입력 사례에 대한 실행 시간을 계산해야 한다.

일반적으로 동일한 크기의 모든 입력이 동등한 확률로 발생한다고 가정한다.

 

분할 상환 실행시간은 관련된 작업의 일련의 연산에 대해 평균 실행 시간을 계산한다. 

분할 상환 분석은 일련의 연산들에 대해 평균적으로 비용이 낮다는 것을 보장한다.

개별 작업은 가끔 비쌀 수 있지만, 전체 작업의 평균 비용은 여전히 작다. 

분할 상환 분석은 최악의 경우에도 각 작업의 평균 성능을 보장한다.

 

<예시>

 

리스트에서 최소 요소를 찾는 문제

• 최악: $O(n)$
• 평균: $O(n)$

퀵 정렬

• 최악: $O(n^2)$
• 평균: $O(n \log n)$

합병 정렬, 힙 정렬

• 최악: $O(n \log n)$
• 평균: $O(n \log n)$

버블 정렬

• 최악: $O(n^2)$
• 평균: $O(n^2)$

이진 탐색 트리에서 요소 검색

• 최악: $O(n)$
• 평균: $O(\log n)$

---

** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.

틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **