[알고리즘] 분할상각기법 Amoritized Analysis

📂 분할상각기법

어떠한 임의의 알고리즘에 대해서, 어떤 연산은 자원적 측면에서 상당한 비용을 소모할 수 있지만, 반면 다른 연산은 그렇게 고비용을 소모하지 않을 수 있다. 분할상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하는 기법이라 하겠다. 이것은 다른 종류의 입력, 입력의 길이, 이 알고리즘의 성능에 영향을 미치는 다른 요인들을 전부 고려한다. 수행된 모든 연산에 대해 자료구조 연산만의 어떤 시퀀스를 수행하는데 필요한 시간의 평균을 구한다. 비록 그 시퀀스에서 하나의 연산비용이 비싸더라도, 그 일련의 연산에 대해 평균을 구하면 연산 하나의 평균 비용이 작다는 것을 분할 상환 분석을 이용해 보일 수 있다. 분할 상환 분석은 확률이 포함되지 않으므로 평균비용 분석과는 다르다. 분할 상환 분석은 최악의 경우에도 각 연산의 평균 수행성능을 보장한다.
- 위키백과 '분할상환분석' 中

분할상환분석이라고도 부르며 Amoritized Analysis 기법이라고 주로 부른다. 빅오표기법의 점근적분석(Asymptotic Analysis)와는 반대되는 개념이라고 봐도 되겠다. 평소엔 O(1)의 시간이 소요되다가 정말 가끔 O(n)의 시간이 소요되는 알고리즘의 경우, 빅오표기법에서는 O(n)으로 시간복잡도를 표현한다. 그러나 평균적으로 O(n)은 아주 가끔 발생하므로 그리 성능이 나쁜 알고리즘이 아닐지도 모른다. 이런 점에서 빅오표기법을 사용하면 시간적 부분에서 불공정한 성능 평가가 이루어질 수 있으므로 등장한 것이 분할상각기법이다. 

테이블에 item을 입력하는 과정에서 대부분 테이블의 크기는 일정하다. 그러나 가끔 테이블이 full 상태가 되면 item 모두를 새로운(2배 더 넓은) 테이블로 옮겨야한다. n개의 item을 2n 크기의 테이블로 옮기는 과정에서 평소보다 많은 시간이 소요된다. 이렇게 가끔 발생하는 시간 불균형을 과정의 모든 단계로 분산해 평준화시키는 것이 이 알고리즘의 핵심이다.

Amoritized Cost = Actual Cost + Accounting Cost 

여기서 Accounting Cost는 회계비용이라고 하며, 모든 단계에 배분될 비용을 의미한다.

item 하나를 새로운 테이블에 옮길때 t 시간이 소요된다고 하자. 그럼 n개의 item을 옮기려면 총 tn의 시간이 필요하다. 이때의 tn은 '현재' 테이블 자리가 부족해 기존 데이터를 다른 테이블로 옮기는 비용이다.

더 나아가 생각해보면, 현재가 아니라 이전까지 테이블의 크기가 처음부터 n이 아니었을 수 있다. 이전의 테이블에서는 n/2, 그 전에는 n/4의 크기의 테이블이 데이터 저장자리가 부족해 doubling 되어 지금의 n 크기의 테이블로 온 경우를 생각해볼 수 있다. 이런 경우, 이전까지 테이블의 크기가 doubling 된 경우의 비용 합은 다음과 같다.

tn/2 + tn/4 + tn/8 + ... ≤ tn

과거의 테이블 doubling 비용을 모두 더해도 최대 tn이므로, 현재 + 과거 비용은 2tn이 된다. 이 비용을 전체 과정에 분배해 평준화시켜야 하므로 2tn / n = 2t 의 Accounting Cost를 도출할 수 있다.

1. table이 full이 아닐 때 : 아이템 입력시간 O(1) 과 Accounting Cost(2t)를 더해 1 + 2t 비용이 필요하다
2. table이 full일 때 : 아이템 입력시간 O(1)과 Transferring Cost(tn)을 더해 (1+tn)이 되는데, Accounting Cost(2t)와 다른단계에서 더해줬던 tn을 감산해 (2t - tn)이 Accouting Cost로 더해져 총 1 + 2t의 비용이 필요하다

따라서 최악의 경우의 비용을 평준화한 결과 O(1 + 2t) = O(1)의 비용이 도출된다. 

분할상각기법에서는 Amoritized O(1) 이라고 표시하여 빅오표기법과의 혼란을 피한다.

 

두서없이 내가 이해한 내용을 정리했지만 더 깊이 이해하려면 좀 멀었다.

해시 알고리즘에서 교수님이 해시테이블의 크기를 2배로 늘려야 하는 이유에서 분할상각기법을 언급하셨다. +c 상수만큼의 공간을 늘리는 것보다 2배 확장하는 것이 더 효율적이라는 것이다. Array Doubling 개념은 분할상각기법에서도 과거의 테이블 확장 비용 합을 구할때 사용된다. 명확하게 딱 정의하고 설명하기는 힘들지만 대강 어떤 원리로 분할상각기법을 사용하는지 이해한듯하다..

 

출처

8iggy.tistory.com/25

ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0%EC%83%81%ED%99%98%EB%B6%84%EC%84%9D

zeddios.tistory.com/62