[번역 - Cornell Univ.] 분할 상환 분석 (Amortized Analysis)

출처 : http://www.cs.cornell.edu/courses/cs3110/2011sp/Lectures/lec20-amortized/amortized.htm

Lecture 20: Amortized Analysis

l  Introduction

-      hash table은 저장된 원소들의 개수의 bucket*의 개수가 비슷한 가정하에 탐색과 삽입의 시간 복잡도가 O(1)이 된다. (hash bucket : key와 hash function에 의해 도출된 값이 저장되는 공간을 일컫는 듯) 그러나 bucket보다 더 많은 데이터들을 저장하여 bucket이 커질 경우, O(n)이 될 수 있다.

-      이를 해결하기 위한 방법으로, table의 데이터가 커지면 table 사이즈를 늘리는 방법이 있음. (load factor : bucket 수에 대한 데이터의 수의 비율). load factor가 특정값을 넘기면, 기존 table의 2배에 해당하는(doubling) 새로운 table을 할당. (보통 chaining에서는 2, linear probing에서는 0.75). 이럴 경우 상수 시간에 해결되지 않으며, table이 커질 때 데이터 개수에 linear한 선형 시간을 갖는다.

-      resizing으로 인한 선형 시간은 생각보다 큰 문제가 아니다. 위처럼 필요할 때마다 doubling이 발생하면, doubling이 발생하는 횟수는 지수적으로 감소한다. 결론적으로, 빈 array에 n개 데이터가 삽입되는 순간만 resizing cost를 포함하여 O(n)의 시간이 걸리는 것이다. 이는 몇몇 데이터의 삽입이 모든 데이터의 rehasing을 trigger시킨다 하더라도, 평균적으로 O(1)의 시간이 걸리므로, 우리는 O(1)의 amortized run time을 갖는다고 한다.

-      여기서 중요한 점은 doubling이 일어난다는 점이다. 지정된 값(ex. array가 넘칠 때마다 100개씩 증가)으로 증가할 경우, 이는 점진적 선형 시간을 갖게 될 것이다.

 

l  Amortized Analysis

-      Amortized Analysis는 일련된 연산(Sequence of Operation)의 최악의 경우 분석이다. Amortized Analysis는 cost의 bound를 이 일련된 연산의 전체적 또는 평균적으로 얻지 않고, 각 연산에 대해 나누어 분석하여 얻는다.

-      Amortized Analysis를 위해 아래 3가지가 사용됨

1)    Aggregate method
일련된 연산의 종합 실행시간(total running time)이 분석되어 있는 것

2)    Accounting(or Banker’s) method
cost가 많이 필요한(expensive) 연산에 사용하기 위해, cost가 많이 필요없는(inexpensive) 연산에 대해 저렴한 cost(extra charge)를 부과하는 것

3)    Potential(or Physicist’s) method
여기서 각 step의 추가작업 양에 대한 potential function을 정의, 마이너스 값은 될 수 없지만 연속된 연산속에서 증감할 수 있음

-      크기를 선언하지 않는, 즉 임의의 크기를 갖는 extensible array를 생각해보자. 예를 들어, Java에서는 ArrayList와 Vector가 있는데, 이들은 평범한 non-extensible array로 구현되었다. add operation은 삽입된 데이터 뒤에 새로운 데이터를 삽입한다. 만약 삽입할 공간이 없다면, double size의 새로운 array를 할당하고 기존 array의 모든 데이터를 이 array로 copy한다.

 

l  Aggregate Method

-      Doubling array에 사용되는 cost를 정의

ci를 다음과 같이 정의
if i-1이 2의 거듭제곱일 경우 i, else 1

-       si를 table의 size라 할 때, i=10까지 insertion 예시

-       di를 doubling의 cost라 할 때, ci = 1 + di로 정의하며, di를 다음과 같이 정의

-       n까지 cost의 합을 ci(left)와 di(right)로 표현하면 아래와 같음, m = log(n-1)

이 때 왜 2j-1인이 모르겠음, 2j 아닌가?

-      따라서, right에서 등비수열의 합을 대입했을 때, O(n) + O(n)이므로, left도 O(n)

 

l  Accounting method

-      Aggregating method에서 일련된 연산들의 전체적인 실행 시간 bound를 찾았다. 반대로, accounting method는 각각 연산에 청구된(charged) 수많은 잔여 시간들의 payment를 찾는다. 직관적으로, bank account를 생각해보자. Low cost의 연산들은 실제보다 조금 더 큰 cost로 청구되고, 초과량은 이후 사용하기위해 bank account에 예금한다. High cost 연산들은 실제보다 적은 cost로 청구되고, 모자란 부분은 bank account에 저축한 것들로 지불한다. 이를 통해 high cost 연산들의 cost를 전반에 걸쳐 퍼뜨릴 수 있다. 각 연산에 대한 요금(charge)은 bank account의 잔액(balance)이 항상 양의 값을 가질 수 있도록 충분히 커야하고, 실제 cost보다 너무 크지 않게 충분히 작아야 한다.

-      중요한 점은 여기서 각 연산에 청구된 시간이 실제로 해당 연산의 수행시간이 아니라는 점이다. 이는 그저 분석을 쉽게 하기 위한 accounting 기법이다.

-      c’i를 i번째 연산에 대한 요금, ci를 실제 cost라 할 때 아래와 같다.
Σ1≤i≤n ci ≤ Σ1≤i≤n c'i

-      모든 n에 대하여, “일련된 n개 연산의 amortized time이 실제 시간의 bound다”라 할 수 있다.

extensible array 예제로 돌아가자. 요소 삽입의 cost와 doubling으로 인한 요소 이동의 cost가 각각 1이라고 하자. 이때 각 삽입마다 1 cost는 매우 작은 요금이다. 그 이유는 이동에 대해 지불할 돈이 남지 않기 때문이다. 2 cost 또한 너무 작다. 만약 요금이 3 cost라 하면 아래와 같다. 여기서 bi는 i번째 삽입 후의 잔액이다.

-      사실 이는 일반화하기에 충분하다. m을 삽입된 m번째 요소라 하자. m에 청구된 3 cost는 아래와 같이 사용된다.

n  1 cost는 table에 m을 즉시 삽입할 때 사용

n  1 cost는 m이 삽입된 후 table이 처음 커지면서 m을 옮길 때 사용

n  1 cost는 m – 2k번째 요소에게 기부되어, table이 처음 커지면서 이를 옮길 때 사용
(2k는 m을 넘지 않는 2의 거듭제곱의 최대값)

-      이제 어떤 요소가 옮겨지더라도, 모든 이동에 대해 이미 cost가 지불되어있다. 어떤 요소가 처음 옮겨질 때, 스스로 가진 요금중에 일부로 지불한다. 이후에 옮겨질 때에는 이후에 삽입된 원소의 기부로 지불한다.

-      아주 조금 더 좋은 방법은, 첫 삽입에는 1 cost를, 그 이후 각 삽입에는 3 cost 청구하면 되는데, 그 이유는 첫 삽입에는 copy에 대한 cost가 없기 때문이다. 이는 첫 삽입에만 잔액이 0원이고, 그 이후에는 양수가 유지될 것이다.

 

l  Potential Method

-      위에서 extensible array를 다루기 위해 aggregate method와 accounting method를 살펴봤다. 이제 potential method를 살펴보자

-      먼저 우리는 아래 특성으로 자료구조의 상태에 대한 potential function Φ를 정의할 수 있다.

n  Φ(h0) = 0, h0는 자료구조의 초기 상태

n  Φ(ht) ≥ 0, ht는 계산과정동안 일어나는 자료구조의 모든 상태를 의미

-      직관적으로, potential function은 계산의 어떤 시점에서든 미리 청구된 시간을 계속 추적한다. 그리고 cost가 큰 연산에 지불할 수 있는 time이 얼마인지 측정한다. 이는 bank account의 잔액과 비슷하다. 그러나 이는 현재 자료구조의 상태에만 의존하며, 현재 상태를 만든 과거 계산은 무시한다.

-      이제 연산의 amortized time을 정의하면 다음과 같다.
c + Φ(h') − Φ(h)

-      c는 연산의 실제 cost, h와 h’은 각각 해당 연산의 이전/이후 자료구조의 상태다. 즉, amortized time은 실제 시간과 잠재적 요금의 합이다. 이상적으로, 각 연산의 amortized time은 작도록 Φ가 정의되어야 한다. 그러므로 potential에서의 차이는 low cost 연산에서 양수, high cost 연산에서 음수가 되어야 한다.

-      이제 일련의 n 연산이 c0, c1, c2, …, cn-1의 실제 시간이 걸리고, h0를 시작으로 자료구조 h1, h2, …, hn을 도출한다 하자. 총 amortized time은 각각 amortized time의 합이다.
(c0 + Φ(h1) − Φ(h0)) + (c1 + Φ(h2) − Φ(h1)) + ... + (cn−1 + Φ(hn) − Φ(hn−1))
= c0 + c1 + ... + cn−1 + Φ(hn) − Φ(h0)
= c0 + c1 + ... + cn−1 + Φ(hn)

-      그러므로 일련의 연산에 대한 amortized time은 Φ(hn)만큼 실제 시간을 초과한다. 이는 가정에 의해 항상 양의 값이다. 그래서 총 amortized time은 항상 실제 시간보다 상한이다.

-      doubling으로 인해 동적으로 resize하는 array에 대해, 아래와 같은 potential function을 사용할 수 있다.
Φ(h) = 2n − m

-      n은 현재 요소의 번호이고, m은 현재 array의 크기이다. 만약 크기가 0부터 시작하여 첫 요소가 삽입되어 길이 1의 array가 할당되고, 그 이후 필요할 때마다 doubling을 한다면, 모든 t에 대해 아래 식이 성립된다.
Φ(h0) = 0 and Φ(ht) ≥ 0

-      원소개수가 항상 최소 array의 반 이상이므로, Φ(ht) ≥ 0가 성립된다.

-      이제 amortized constant time이 걸리는 원소의 삽입을 보자. 아래와 같이 2가지 경우가 있다.

n  n < m이면, 실제 cost는 1이고, n이 1 증가하며, m은 바뀌지 않는다. 그리고 potential은 2 증가하므로, amortized time은 1 + 2 = 3이다.

n  n = m이면, array doubling이 발생하고, 실제 시간은 n+1이다. 그러나 potential이 n에서 2로 떨어지므로, amortized time은 n + 1 + (2 – n) = 3이다.

-      두 경우 모두 amortized time은 O(1)이다.

-      potential method를 이용한 amortized analysis에서 중요한 것은 정확한 potential function의 정의이다. potential function은 필요할 때 사용할 수 있는 충분한 시간을 저축하는 것이 필요하다. 그러나 현재 연산의 amortized time이 너무 커지기 때문에, 큰 시간을 저축할 순 없다.

 

 

  이거 읽느라 너무 많은 시간을 소비하여.... 이해한 내용은 나중에 정리해야겠다 ㅠㅠ 사실 읽어봐도 정확히 이해하기 어렵다. 갑자기 수식이 깜빡이도 틀지 않고 튀어나와서, 정의해주신 수식 보면서 "맞는 말 같다"라는 생각만 한 듯 하다. 이러한 방식으로 내가 직접 도출해내기는 쉽지 않을 듯 하다.
  아래 다른 분이 아주 쉽게 잘 설명해주신 내용도 읽어봤는데, 이들을 종합해서 깔끔하게 한 번 정리해야겠다!

[1] https://zeddios.tistory.com/62

알고리즘 ) Array Doubling/분할상환분석

[2] https://zeddios.tistory.com/60

알고리즘 ) Amortized Analysis

[3] https://www.geeksforgeeks.org/analysis-algorithm-set-5-amortized-analysis-introduction/

Analysis of Algorithm | Set 5 (Amortized Analysis Introduction) - GeeksforGeeks