[알고리즘 6강] 상각 분석법

GisangLee·2023년 10월 3일
0

대학원

목록 보기
7/18
post-custom-banner

1. 개념

알고리즘의 시간 복잡도를 분석하는 기법

  • 연산의 수행 횟수/시간이 독립적으로 결정되지 않고 가변적인 경우

    • 앞서 수행된 연산에 따라 실행 시간이 달라질 때,
      실제 최악 수행 시간을 보다 더 정확하게 분석하는 방법.

상각 분석법의 종류

  • 합계 분석

    • 알고리즘에서 해당 연산의 호출 전체에 대한 최악의 수행시간을 분석하고,
      이를 호출 횟수로 나누어 상각시간을 계산
  • 회계 방법

    • 먼저 사용하는 연산 종류별로 상각 시간을 할당하고,
      실제 연산을 수행할 때 생성되는 자료구조에 회계 장부를 만들어
      예치와 인출을 통ㅌ해 관리하는 방법
  • 위치 에너지 방법

    • 각 연산에 상각 시간을 할당하고 남는 상각 시간을 위치 에너지로 보관하거나
      실제 수행 시간에 모자라는 시간을 위치 에너지에서 빼서 보충하는 방법

2. 합계 분석

최악의 실행 시간 T(n)T(n)

  • 각 연산이 포함되는 일련의 연산 전체가 실행될 때 걸리는 최대 시간
  • 각 연산의 상각 시간
    • 최악의 실행 시간 / 적용된 연산 개수 -> T(n)/nT(n) / n
    • 최악의 경우에 대한 평균값

특징

  • 평균값, 하지만 최악의 경우에 대한 값
  • 연산의 종류를 구분하지 않고, 모든 연산이 하나의 상각 시간을 가짐

변형된 스택 연산

MultiPop(S, k) {
	while not Stack-Empty(S) and k != 0
    	do Pop(s)
        	k = k-1
}
  • 빈 스택에서 Push, Pop, MultiPop으로 구성된 n개의 연속된 연산을 처리하는데 걸리는 시간
    • 스택에 최대의 n개의 객체가 들어갈 수 있으므로
      MultiPop 연산을 1회 실행하는 최악의 시간은 O(n)O(n)
    • 이와 같은 연산이 n번 반복되는 경우가 최악이고 수행 시간은 O(n2)O(n^2)
  • 합계 분석에 의한 상각 분석
    • MultiPop 내부에서 호출되는 Pop을 포함하여
      Pop이 호출될 수 있는 최대 횟수는 최대 Push의 개수와 같으므로
      최대 n이 되고, n번 연산의 최악 수행 시간은 O(n)O(n)이다.
  • 각 연산의 평균 수행 시간
    • O(n)/nO(n)/n = O(1)O(1)

이진 카운터

A[k1]A[k]....A[1]A[0]=x=i=0k1A[i]2iA[k-1]A[k]....A[1]A[0] = x = \displaystyle\sum_{i=0}^{k-1}{A[i]*2^i}

Increment(A){
	i = 0
    while i < length[A] and A[i] == 1 {
    	do A[i] = 0
        i = i + 1
    }
    if i < length[A] {
    	then A[i] = 1
    }
}
  • 수행 시간

    • 바뀐 비트의 개수
  • 초기 상태에서 n번 수행할 때, 1회 연산의 상각 시간?

  • 기본 적인 분석

    • 최악의 경우는 모든 비트가 1인 경우 -> θ(k)\theta(k)
    • n번 Incremenet 연산의 수행 시간 -> O(nk)O(nk)
  • 합계 분석에 의한 상각 분석

    • 1번 수행할 때 변하는 비트의 개수

      • 0ilgn0 \leq i \leq \lfloor{lgn}\rfloor 이면 A[i]A[i] -> n/2i\lfloor{n / 2^i}\rfloor
      • lgn<i\lfloor{lgn}\rfloor < i이면 A[i]A[i] -> 0번

    • n번 수행할 때 변하는 횟수

      • i=0lgnn2i<i=012i=2n\displaystyle\sum_{i=0}^{\lfloor{lgn}\rfloor}{\lfloor{\frac{n}{2^i}}\rfloor} < \displaystyle\sum_{i=0}^{\infty}{\lfloor{\frac{1}{2^i}}\rfloor} = 2n
    • 1회 연산에 대한 상각 시간

      • O(n)/n=O(1)O(n)/ n = O(1)

3. 회계 방법

회계 (accounting) 계정 처리와 유사한 개념을 사용

  • 각 연산마다 적절한 자본금을 미리 정해 할당

    • 자본금 = 상각 시간

    • 각 연산별로 다른 상각 시간을 가짐

      • 연산의 실제 비용 < 자본금 -> 남는 금액(시간)을 예금
      • 연산의 실제 비용 > 자본금 -> 부족한 금액을 인출
  • 최악의 실행시간의 상한
    • 알고리즘에서 적용된 연산들의 자본금 합계

변형된 스택 연산

각 연산바마다 상각 시간 할당

연산명실제 수행시간할당한 상각 시간
Push1122
Pop1100
MultiPopmin(k,s)min(k, s)00
  • Push 연산

    • 1원 -> 실제 Push 연산 수행을 위해 지불
    • 1원 -> Pop 연산을 대비해서 미리 지불한 돈
  • Pop, MultipPop 연산 -> 상각 시간 불필요

  • 임의의 n개의 연산들에 대한 상각 시간의 합이 실제 연산 시간의 상한

    • 총 상각 시간의 합 O(n)O(n)
      • 실제 연산 시간의 합 O(n)O(n)

이진 카운터

  • 수행 시간

    • 바뀐 비트의 개수
  • 비트의 값을 1로 바꿀 때 상각 시간 2원 할당

    • 0에서 1로 바꿀 때
      • 1원 -> 해당 비트를 세팅하는 데 사용
      • 1원 -> 나중에 해당 비트를 다시 0으로 바꿀 때 사용
    • 1에서 0으로 바꿀 때
      • 해당 비트에 저장된 1원 사용 -> 별도의 상각 시간 불필요
  • 1회 연산의 최대 상각 시간 2원

    • n번 연산의 최대 상각 시간 -> O(n)O(n)

4. 위치 에너지 방법

각 종류의 연산마다 상각 시간을 할당 ( 회계 방법과 여기까지는 동일 )

  • 각 객체에 대한 남는 상각 시간을 저장하지 않음
    • 전체 자료구조에 대하여 남는 상각 시간을 위치 에너지처럼 생각하고 저장한다.
  • i번 째 연산의 상각 시간

    • i번째 연산의 실제 수행 시간 + 위치 에너지의 변화량

    • Ci^=Ci+ϕ(Di)ϕ(Di1)\hat{C_i} = C_i + \phi(D_i) - \phi(D_{i-1})

      • DiD_i : Di1D_{i-1}에 i번째 연산이 수행된 상태의 자료구조
      • ϕ(Di)\phi({D_i}) : 자료구조 DiD_i를 실수값으로 변환하는 함수
  • 최악 수행 시간의 상한

    • n개의 연산에 대한 상각 시간의 총합

    • i=1nci^=i=1n(ci+ϕ(Di)ϕ(Di1))=i=1nc+ϕ(Dn)ϕ(D0)\displaystyle\sum_{i=1}^n{\hat{c_i}} = \displaystyle\sum_{i=1}^{n}(c_i + \phi({D_i})- \phi(D_{i-1}))\\ = \displaystyle\sum_{i=1}^{n}{c + \phi(D_n)-\phi(D_0)}

      • ϕ(D0)=0\phi(D_0) = 0으로 정의, ϕ(Di)0\phi(D_i) \geq 0임을 보임
  • 상각 분석 과정

    • 위치 에너지 함수 ϕ\phi 정의

      • 모든 i에 대해 ϕ(Di)ϕ(D0)=0\phi(D_i) \geq \phi(D-0) = 0 을 만족
    • 연산의 상각 시간을 계산

      • ci^=ci+ϕ(Di)ϕ(Di1)\hat{c_i} = c_i + \phi(D_i) - \phi(D_{i-1})
    • 적된 연산들에 대한 상각 시간의 합 i=1nci^\displaystyle\sum_{i=1}^{n}{\hat{c_i}} 를 최악의 시간 복잡도로 취함

변형된 스택 연산

ϕ\phi -> 스택에 들어있는 객체의 개수

  • ϕ(D0)=0\phi(D_0) = 0,\quad ϕ(Di)0=ϕ(D0)\phi(D_i) \geq 0 = \phi(D_0)
  • Push 연산 (스택에 s개의 객체가 있는 경우)

    • ϕ(Di)ϕ(Di1)=(s+1)s=1\phi(D_i) - \phi(D_{i-1}) = (s+1) - s = 1
      • ci^=ci+ϕ(Di)ϕ(Di1)=1+1=2\hat{c_i} = c_i + \phi(D_i) - \phi(D_{i-1}) = 1 + 1 = 2
  • MultiPop 연산

    • ϕ(Di)ϕ(Di1)=k=min(k,s)\phi(D_i) - \phi(D_{i-1}) = k^{\prime} = min(k, s)
      • ci^=ci+ϕ(Di)ϕ(Di1)=kk=0\hat{c_i} = c_i + \phi(D_i) - \phi(D_{i-1}) = k^{\prime} - k^{\prime} = 0
  • 각 연산의 상각 시간
    • n개의 연산에 대한 최악의 수행 시간 : O(n)O(n)

이진 카운터

ϕ(Di)=bi\phi(D_i) = b_i

  • bib_i: \quad i번째 연산 종료 후 상태 DiD_i에서 값이 1인 비트의 개수
  • Increment 연산의 실제 연산 시간 : 최대 ti+1t_i + 1
    • 리셋 되는 비트의 개수(tit_i) + 1로 바꾸는 비트의 연산
  • 위치 에너지의 변화량
    • ϕ(Di)ϕ(Di1)(bi1ti+1)bi1=1ti\phi(D_i) - \phi(D_{i-1}) \leq (b_{i-1} - t_i + 1) - b_{i-1} = 1 - t_i
  • 상각 시간
    • ci^=ci+ϕ(Di)ϕ(Di1)(ti+1)+(1ti)=2\hat{c_i} = c_i + \phi(D_i) - \phi(D_{i-1}) \leq (t_i + 1) + (1 - t_i) = 2
    • n번 연산의 최악의 수행 시간 : O(n)O(n)

5. 동적 테이블을 분석해보자

저장된 객체가 늘어남에 따라 테이블의 크기가 커지는 테이블

  • 테이블의 확장 -> 테이블의 크기를 늘리는 과정

동적 테이블에 데이터를 삽입하는 경우 수행 시간?

  • 이미 사용하던 테이블의 2배 공간을 할당하고,
    기존 객체들을 새 공간에 복사한다.
    • 특징
      • 삽입 연산만 수행할 경우, 항상 테이블의 절반 이상이 사용됨.
Table-Insert(T, x) {
	if size[T} == 0 {
    	table[T]에 1개까리 공간을 할당;
        size[T] = 1;
    }
    
    if num[T] == size[T] {
    	temp = 크기가 2*size[T]인 새로운 공간 할당;
        table[T]에 있던 객체들을 temp에 삽입;
        table[T]의 공간을 반환(free);
        table[T] = temp;
        size[T] = 2 *size[T];
    }
    
    table[T]에 x를 삽입;
    num[T] = num[T] + 1
}

// num[T] : 들어있는 객체의 수

기존 분석

  • 최악의 경우 1번의 삽입 연산 : O(n)O(n)

    • i번째 삽입에서 테이블이 꽉 찬 경우 기존 테이블에서 i-1 객체들을 옮기고,
      1개의 객체를 추가 -> ci=ic_i = i
  • n번의 삽입 연산의 시간 복잡도 : O(n2)O(n^2)

합계 분석

  • n번의 삽입 연산

    • i=1ncin+j=1lgn2j<n+2n=3n\displaystyle\sum_{i=1}^{n}{c_i}\leq n + \displaystyle\sum_{j=1}^{\lfloor{lgn}\rfloor}2^j < n + 2n = 3n
  • 삽입 연산의 상각 시간 : 3n/n=33n / n = 3 -> O(n)O(n)

회계 방법

  • 삽입 연산의 상각 시간 : 3원

    • 1원 : 자신을 삽입할 때 사용
    • 1원: 테이블 확장 시 자신을 새로운 테이블로 이동할 때 사용
    • 1원: 기존 테이블에 있었던 다른 1개의 객체를 옮기는 데 사용
  • 확장 직후 테이블의 크기 m

    • 객체의 수는 m/2 이며, 모든 상각 시간을 소비한 상태
    • 객체가 삽입될 때마다 1원은 자신의 삽입을 위해 소비
      • 1원: 다음 확장을 위해 자신이 저장
      • 1원: 저장된 상각 시간이 0인 객체에 저장
  • m/2번 삽입

    • m개의 모든 객체가 1원을 가짐
    • 2m으로 확장/이동 가능
  • 삽입 연산의 상각 시간 -> O(n)O(n)

위치 에너지 방법

  • ϕ(T)=2num[T]size[T]\phi(T) = 2 * num[T] - size[T]

    • 테이블 확장 직후 num[T]=size[T]/2num[T] = size[T] / 2 -> ϕ(T)=0\phi(T) = 0
    • 테이블이 꽉찬 경우 num[T]=size[T]num[T] = size[T] -> ϕ(T)=num[T]\phi(T) = num[T]
  • num0=0num_0 = 0, size0=0size_0 = 0, ϕ0=0\phi_0 = 0

    • i번째 연산에 의해 테이블이 확장되지 않은 경우 : sizei=sizei1size_i = size_{i-1}
      • ci^=ci+ϕiϕi1=1+(2numisizei)(2numi1sizei1)=1+(2numisizei)(2numi1)sizei)=3\hat{c_i} = c_i + \phi_i - \phi_{i-1}\\ =1 + (2 * num_i - size_i) - (2 * num_{i-1} - size_{i-1})\\ = 1 + (2 * num_i - size_i) - (2 * num_i - 1) - size_i)\\ = 3

    • i번째 연산에 의해 테이블이 확장되지 않은 경우
      • sizei=2(numi1)size_i = 2 * (num_i - 1), \quad sizei1=numi1=numi1size_{i-1} = num_{i-1} = num_i - 1
      • ci^=ci+ϕiϕi1=numi+(2numisizei)(2numi1sizei1)=numi+(2numi2(numi1))(2numi1)(numi1))=3\hat{c_i} = c_i + \phi_i - \phi_{i-1}\\ =num_i + (2 * num_i - size_i) - (2 * num_{i-1} - size_{i-1})\\ = num_i + (2 * num_i - 2 * (num_i - 1)) - (2 * num_i - 1) - (num_i - 1))\\ = 3
  • 삽입 연산의 상각 시간 : 3 -> O(n)O(n)


profile
포폴 및 이력서 : https://gisanglee.github.io/web-porfolio/
post-custom-banner

0개의 댓글