[CLRS] [16] Amortized Analysis (분할 상환 분석)

1. Amortized Analysis?

- 분할 상환 분석(Amortized Analysis)에 대해서 알아보자.

- Amortized Analysis는 알고리즘의 시간 복잡도를 분석하는 방법 중 하나로, 특정 연산의 평균 실행 시간을 계산하는 데 초점을 둠

- 이는 최악의 경우 시간 복잡도를 항상 고려하는 Worst-case Analysis와 달리, 일련의 연산이 여러번 반복되는 경우 전체 작업에 대한 총 수행 시간을 분석하여 ''연산당 평균 비용''을 구하는 데 초점을 맞춘다.

 

2. Amortized Analysis가 필요한 이유

- 어떤 데이터 구조나 알고리즘에서는 일부 연산이 매우 비싸지만, 다른 연산들은 거의 비용이 들지 않는 경우가 있다.

ex) 동적 배열, Hash table...

- 이때 단순히 최악의 경우를 분석하면 평균적인 동작 성능을 제대로 설명하지 못한다.

- 예를 들어 동적 배열(Array List)을 생각해보자.

 

1. 동적 배열에 항목을 추가할 때, 배열이 가득 차 있지 않다면 삽입은 O(1)에 수행된다.

2. 하지만 배열이 가득 찼을 경우, 새 배열을 할당하고 모든 기존 항목을 복사해야 하므로 삽입연산은 O(N)이 된다.

 

- 단지 최악의 경우만 본다면 '삽입은 O(N)'이라는 결론을 짓게되지만, 현실에서는 배열 크기를 확장하는 것은 드물다.

- 대부분의 삽입은 O(1)으로 이루어지기 때문에, Amortized Analysis를 통해 O(1)이라고 분석할 수 있는 것이다.

 

3. Amortized Analysis의 주요 기법

3.1. Aggegate Analysis(총합 분석)

- 핵심 아이디어는 다음과 같다.

- 전체 연산의 총 실행시간을 계산한 후, 개별 연산의 평균비용을 구하는 방식이다.

 

절차 :

- 1. n번의 연산이 수행되는 동안 발생하는 총 시간 비용을 계산

- 2. 이를 n으로 나누어 연산당 평균 비용(Amortized Cost)을 계산

 

예제를 통해 자세히 알아보자.

 

예제 : 동적 배열에서의 삽입

- 동적 배열의 초기 크기는 1이고, 배열이 가득 차면 두 배로 확장.

- 삽입 연산의 비용 :

-- 대부분의 삽입 : O(1)

-- 배열 확장이 필요할 때 : O(N) cf) 모든 요소를 새 배열로 복사

 

분석 : 

- n개의 삽입 연산중 배열확장은 1, 2, 4,... 2**n 형태로 발생

-  총 복사 비용은 1 + 2 + 4 + ... + n <= 2n

- n개의 삽입연산에 대한 총 비용 : O(2n) = O(n)

- 평균 비용 : O(n) / n = O(1)

 

3.2. Accounting Method

- 핵심아이디어는 다음과 같다.

- 각 연산에 'credit'을 부과하여 비싼 연산의 비용을 미리 분산시키는 방법.

- 마치 '적금'처럼 평소 저렴한 연산에서 남은 잉여 자원을 비싼 연산에 사용한다고 볼 수 있다.

 

절차 : 

- 1. 각 연산에 가상의 비용(credit)을 할당.

- 2. 저렴한 연산에서는 남는 비용을 저장(credit 축적).

- 3. 비싼 연산에서 저장된 credit을 사용하여 실제 비용 충당.

 

예제 : 동적 배열 삽입

- 배열 확장 시 발생하는 복사 비용을 감안하여, 각 삽입 연산에 credit을 부과.

 

분석 : 

- 1. 평범한 삽입 : 삽입에 1의 실제 비욜이 발생, credit으로 1을 추가 부과

-- 총 2의 비용이 발생하지만, 그중 1은 credit으로 저장

 

- 2. 배열 확장 : 크기 k인 배열 확장에서 k개의 복사 비용 발생

-- 이전 삽입에서 저장한 k만큼의 credit으로 충당

 

결론 :

- 각 삽입 연산의 Amortized Cost는 O(1)이다.

 

3.3. Potential Method

- 데이터 구조의 현재 상태를 나타내는 potential function을 정의하여, 상태 변화와 함께 발생하는 비용을 평가하는방법.

- potential은 데이터 구조의 '저장된 자원'을 나타내며, 이를 통해 연산 비용을 계산한다.

 

- 수식은 다음과 같다.

Amortized Cost = Actual Cost + (Potential Difference)