Amortized analysis (2)

KVV·2024년 11월 6일
알고리즘

Amortized analysis 를 통해 Dynamic tables 문제를 해결해보자.

Dynamic tables

테이블 할당 문제

Operation

  • insertion

    • 새로운 항목이 추가될 때 테이블의 공간을 할당하고, 공간이 꽉 차면 테이블을 재할당해야 한다.

  • deletion

    • 테이블에서 많은 객체가 삭제되었을 때, 더 작은 크기의 테이블로 재할당하는 것이 효율적일 수 있다.

목표

Amortized analysis를 통해 삽입과 삭제 연산의 Amortized cost가 O(1) 임을 증명하자

Aggregate analysis

INSERT

기존 테이블이 꽉차면 기존 테이블의 2배 크기의 새로운 테이블을 재할당하고 기존 테이블의 데이터는 새로운 테이블에 복사하고 새로운 데이터를 추가한다.

사용하는 변수

T.table: 현재 테이블 공간을 가리키는 포인터
T.num: 현재 테이블에 들어있는 데이터 개수
T.size: 현재 테이블의 크기

pseudocode of INSERT

TABLE-INSERT(T, x)
1	 if T.size == 0 //initialize
2    	 allocate T.table with 1 slot
3        T.size = 1
4    if T.num == T.size
5    	 allocate new-table with 2 * T.size slots
6        insert all items in T.table into new-table
7        free T.table
8        T.table = new-table
9        T.size = 2 * T.size
10   insert x into T.table
11   T.num = T.num + 1

elementary insertion: 6, 10 line
expansion: 5~9 lines

Analysis

The actual cost of INSERT

  1. 현재 테이블에 공간이 남아있는 경우

    • cic_i = 1

  2. 현재 테이블에 공간이 남아있지 않는 경우

    • expansion 진행 후, (i-1) 개의 데이터를 복사해야하고, 1개의 데이터를 추가해야한다.
    • cic_i = i

테이블 재할당 크기는 이전 테이블 크기의 2배이므로, (i−1)=2k(i-1) = 2^{k} 인 경우에 ci=ic_i = i 이다.

The total cost of n TABLE-INSERT

∑i=1nci≤n+∑j=0⌊log(n−1)⌋2j≤n+∑j=0⌊logn⌋2j\displaystyle\sum_{i=1}^{n} c_i \le n + \displaystyle\sum_{j=0}^{\lfloor log(n-1) \rfloor} 2^j \le n + \displaystyle\sum_{j=0}^{\lfloor logn \rfloor} 2^j

(∑j=0⌊logn⌋2j=2⌊logn⌋+1−12−1≤2∗2⌊logn⌋≤2n\displaystyle\sum_{j=0}^{\lfloor logn \rfloor} 2^j = \frac{2^{\lfloor logn \rfloor +1} -1}{2-1} \le 2 * 2^{\lfloor logn \rfloor} \le 2n)

∑i=1nci≤n+2n=3n\displaystyle\sum_{i=1}^{n} c_i \le n + 2n = 3n

가장 첫 번째의 n은 O(1)의 TABLE-INSERT가 n개 있다고 가정하여 ≤\le 을 취한 결과이다.

Amortized cost

Total cost of n TABLE-INSERT = O(3n)
Amortized cost of single operation: 최대 3 (3n / n)

Accounting method

pseudocode of INSERT

TABLE-INSERT(T, x)
1	 if T.size == 0 //initialize
2    	 allocate T.table with 1 slot
3        T.size = 1
4    if T.num == T.size
5    	 allocate new-table with 2 * T.size slots
6        insert all items in T.table into new-table
7        free T.table
8        T.table = new-table
9        T.size = 2 * T.size
10   insert x into T.table
11   T.num = T.num + 1

elementary insertion: 6, 10 line

Accounting method를 이용하여 왜 amortized cost of a TABLE-INSERT 가 3인지를 보이자.

  • Line 10: 1 cost
    • Line 10에서 2 credit을 저장한다.
  • Line 6: 2 credit

각 데이터는 3번의 elementary insertions 을 수행하게 된다

  1. 현재 테이블에 해당 데이터를 삽입 (처음 과정)
  2. 테이블이 확장될 시 해당 데이터를 이동시킴
  3. 이미 테이블이 확장되어 한번 이동된 데이터를 테이블이 다시 확장될 때 이동시킴

각 데이터는 3번의 elementary insertions 를 수행하기 때문에 Amortized cost of a TABLE-INSERT는 3이다.

Potential method

numinum_i: i번째 operation 이후 테이블에 들어있는 데이터 개수
sizeisize_i: i번째 operation 이후 테이블의 크기
Φi\Phi_i: i번째 operation 이후 potential
ci^\hat{c_i}: Φi\Phi_i 를 이용하여 구한 amortized cost

num0num_0 = 0, size0size_0 = 0, Φ0\Phi_0 = 0

Φ()\Phi()는 table expansion 직후에 0, table이 가득 찼을 시 table size와 같다고 정의한다.

  • Φ(T)=2∗T.num−T.size\Phi(T) = 2*T.num - T.size
  • 테이블이 항상 절반 이상 채워져있는 상태이기 때문에 T.num≥T.size/2T.num \ge T.size/2
  • Φ(T0)=0\Phi(T_0) = 0

  • 테이블 확장 바로 직전에는 Φi=numi\Phi_i = num_i
  • 테이블 확장 바로 직후에는 0이 되지만, 즉시 2로 되돌아 온다.
    • 2가 되는 이유는 테이블 확장 직후에는 Φ(T)=2∗T.num−T.size=2∗(T.num)−2∗(T.num−1)=2\Phi(T) = 2*T.num - T.size = 2*(T.num) - 2*(T.num-1) = 2

Amortized cost

  1. i번째 operation이 expansion을 발생시키지 않는 경우

    • sizeisize_i = sizei−1size_{i-1}

    • ci^=ci+Φi(T)−Φi−1(T)\hat{c_i} = c_i + \Phi_i(T) - \Phi_{i-1}(T)

    • = 1 + (2∗numi−sizei)(2*num_i-size_i) - (2∗numi−1−sizei−1)(2*num_{i-1}-size_{i-1})

    • = 1 + (2∗numi−sizei)(2*num_i-size_i) - (2∗(numi−1)−sizei−1)(2*(num_{i}-1)-size_{i-1}) = 3

  2. i번째 operation이 expansion을 발생시키는 경우

    • sizeisize_i = 2∗sizei−12*size_{i-1}

    • sizei−1=numi−1=numi−1size_{i-1} = num_{i-1} = num_i -1

    • sizei=2∗(numi−1)size_i = 2*(num_i - 1)

    • ci^=ci+Φi(T)−Φi−1(T)\hat{c_i} = c_i + \Phi_i(T) - \Phi_{i-1}(T)

    • = numinum_i + (2∗numi−2∗(numi−1))−(2∗(numi−1)−(numi−1))(2*num_i-2*(num_i-1))-(2*(num_{i}-1)-(num_i-1))

    • = numinum_i + 2−numi−12 - num_{i}-1 = 3

Amortized cost of INSERTION = O(1)

Dynamic table with expansion and contraction

Table contraction: table에 empty slot이 많을 때, table을 더 작은 사이즈로 재할당하는 것

load factor를 이용한다.

  • α(T)=T.num/T.size\alpha(T) = T.num / T.size
  • 특정 상수 이상의 값을 유지하도록 해야한다. (Bounded below by a positive constant)
    • Load factor ≥\ge k 라면 Load factor = k 일 때, table contraction을 수행한다.
  • Table 연산의 amortized cost는 상수 시간을 넘기면 안 된다. (Bounded above by a constant)
  • 해당 테이블의 밀집도를 나타내는 값으로써 테이블이 얼마나 효율적으로 사용되는지를 나타낸다.

1. Load factor ≥\ge 1/2

  • n = 2k2^k라고 하자
  • 처음 n/2 개의 operation이 모두 insertion이라고 가정하면, n/2 개의 operation 후에는 T.num=T.size=n/2T.num = T.size = n/2 이다.
  • 처음 n/2 개의 operation의 시간 복잡도는 θ(n)\theta(n) 이다.

위의 상태에서 worst case를 확인해보자

  • 나머지 n/2 개의 operation이 [insert, delete, delete, insert, insert, delete, delete, insert, insert, ...] 순서라고 하자]

  • Load factor = 1/2 일 때, table contraction을 수행한다고 가정하고 연산 횟수를 계산해보면 위 그림과 같다.

  • 위 그림에서 나머지 n/2 개의 operation 중 절반이 n/2 번의 연산 횟수를 가진다.

    • O(n/2 * n/4) = O(n2/8n^2/8) = θ(n2)\theta(n^2)

  • 이를 통해 Amortized cost를 구해보면 θ(n2)/n=θ(n)\theta(n^2)/n = \theta(n)

2. Load factor ≥\ge 1/4 (Best case)

potential method 를 사용하여 증명하자

  • α(T)=T.num/T.size\alpha(T) = T.num/T.size
  • Table이 비어있다면, num0=size0=0num_0 = size_0 = 0, α(T)=1\alpha(T) = 1, Φo=0\Phi_o = 0
  • 위의 식을 보면 potential ≥\ge 0 을 만족한다.

TABLE-INSERT

case 1: αi−1≥1/2\alpha_{i-1} \ge 1/2

  • TABLE-INSERT만 존재하는 경우와 동일하다.
  • 위에서 증명한 것과 같이 Amortized cost는 최대 3이다.
  • Table-expansion이 발생하더라도 Load factor ≥\ge 1/2.

case 2: αi−1<1/2\alpha_{i-1} < 1/2

두 가지 케이스로 나눌 수 있다.

case 2-1: αi<1/2\alpha_{i} < 1/2

  • sizei=sizei−1size_i = size_{i-1}

  • numi−1=numi−1num_{i-1} = num_i - 1

  • Amortized cost of the ith operaion

    • ci^=ci+Φi−Φi−1\hat{c_i} = c_i + \Phi_i - \Phi_{i-1}
      = 1 + (sizei/2−numisize_i/2 - num_i) - (sizei−1/2−numi−1size_{i-1}/2 - num_{i-1})
      = 1 + (sizei/2−numisize_i/2 - num_i) - (sizei−1/2−numi+1size_{i-1}/2 - num_i+1)
      = 0

case 2-2: αi≥1/2\alpha_{i} \ge 1/2

  • Amortized cost of the ith operaion
    • ci^=ci+Φi−Φi−1\hat{c_i} = c_i + \Phi_i - \Phi_{i-1}
      = 1 + (2∗numi−sizei2*num_i-size_i) - (sizei−1/2−numi−1size_{i-1}/2 - num_{i-1})
      = 1 + (2∗(numi−1+1)−sizei2*(num_{i-1}+1)-size_i) - (sizei−1/2−numi−1size_{i-1}/2 - num_{i-1})
      = 3∗numi−1−3∗sizei−1/2+33 * num_{i-1} - 3*size_{i-1}/2 +3
      = 3∗αi−1∗sizei−1−3∗sizei−1/2+33 * \alpha_{i-1} * \text{size}_{i-1} - {3 * \text{size}_{i-1}}/{2} + 3
      < 3∗sizei−1/2−3∗sizei−1/2+33 *\text{size}_{i-1} /2 - {3 * \text{size}_{i-1}}/{2} + 3
      = 3
      = O(1)
    • numi=αi∗sizeinum_i =\alpha_i * size_i
    • αi−1<1/2\alpha_{i-1} < 1/2

따라서 TABLE-INSERT의 amortized cost는 최대 3이다. = O(1)

TABLE-DELETE

numi=numi−1−1num_i = num_{i-1} - 1

case 1: αi−1<1/2\alpha_{i-1} < 1/2

두 가지 경우로 나뉜다.

case 1-1: No contraction

sizei=sizei−1size_i = size_{i-1}

amortize cost

  • ci^=ci+Φi−Φi−1\hat{c_i} =c_i + \Phi_i - \Phi_{i-1}
    = 1+(sizei/2−numi)−(sizei−1/2−(numi+1))1 + (size_i/2 - num_i) - (size_{i-1}/2 - (num_i+1))
    = 1+(sizei/2−numi)−(sizei/2−(numi+1))1 + (size_i/2 - num_i) - (size_i/2 - (num_i+1))
    = 2
    = O(1)

case 1-2: contraction

actual cost: ci=numi+1c_i = num_i + 1
sizei/2=sizei−1/4=numi−1=numi+1size_i/2 = size_{i-1}/4 = num_{i-1} = num_i+1

amortize cost

  • ci^=ci+Φi−Φi−1\hat{c_i} = c_i + \Phi_i - \Phi_{i-1}
    = (numi+1)+(sizei/2−numi)−(sizei−1/2−numi−1)(num_i + 1) + (size_i/2-num_i)-(size_{i-1}/2 -num_{i-1})
    = (numi+1)+((numi+1)−numi)−((2∗numi+2)−numi+1)(num_i + 1) + ((num_i+1)-num_i)-((2*num_i + 2) -num_i+1)
    = 1
    = O(1)

case 2: αi−1≥1/2\alpha_{i-1} \ge 1/2

이 경우에는 contraction이 발생하지 않는다.

sizei=sizei−1size_i = size_{i-1}
numi−1=numi+1num_{i-1} = num_i + 1

이 경우 contraction이 발생할 가능성이 없기 때문에, 직관적으로 delete 하는데 소요되는 시간인 O(1)이 필요하다.

따라서 TABLE-DELETE 도 O(1) 이다.

결론적으로 n개의 table 연산이(INSERT, DELETE) 있을 때, 각 operation의 amortized cost는 bounded above by a constant이기 때문에 소요되는 전체 시간은 O(n)이라고 할 수 있다.

profile
KVV
이전 포스트

Amortized analysis (1)

다음 포스트

Graphs

0개의 댓글