1. 개념
알고리즘의 시간 복잡도를 분석하는 기법
상각 분석법의 종류
-
합계 분석
- 알고리즘에서 해당 연산의 호출 전체에 대한 최악의 수행시간을 분석하고,
이를 호출 횟수로 나누어 상각시간을 계산
-
회계 방법
- 먼저 사용하는 연산 종류별로 상각 시간을 할당하고,
실제 연산을 수행할 때 생성되는 자료구조에 회계 장부를 만들어
예치와 인출을 통ㅌ해 관리하는 방법
-
위치 에너지 방법
- 각 연산에 상각 시간을 할당하고 남는 상각 시간을 위치 에너지로 보관하거나
실제 수행 시간에 모자라는 시간을 위치 에너지에서 빼서 보충하는 방법
2. 합계 분석
최악의 실행 시간 T(n)
- 각 연산이 포함되는 일련의 연산 전체가 실행될 때 걸리는 최대 시간
- 각 연산의 상각 시간
- 최악의 실행 시간 / 적용된 연산 개수 -> T(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)
- 이와 같은 연산이 n번 반복되는 경우가 최악이고 수행 시간은 O(n2)
- 합계 분석에 의한 상각 분석
- MultiPop 내부에서 호출되는 Pop을 포함하여
Pop이 호출될 수 있는 최대 횟수는 최대 Push의 개수와 같으므로
최대 n이 되고, n번 연산의 최악 수행 시간은 O(n)이다.
- 각 연산의 평균 수행 시간
- O(n)/n = O(1)
이진 카운터
A[k−1]A[k]....A[1]A[0]=x=i=0∑k−1A[i]∗2i
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
}
}
3. 회계 방법
회계 (accounting) 계정 처리와 유사한 개념을 사용
-
각 연산마다 적절한 자본금을 미리 정해 할당
-
자본금 = 상각 시간
-
각 연산별로 다른 상각 시간을 가짐
- 연산의 실제 비용 < 자본금 -> 남는 금액(시간)을 예금
- 연산의 실제 비용 > 자본금 -> 부족한 금액을 인출
변형된 스택 연산
각 연산바마다 상각 시간 할당
연산명 | 실제 수행시간 | 할당한 상각 시간 |
---|
Push | 1 | 2 |
Pop | 1 | 0 |
MultiPop | min(k,s) | 0 |
이진 카운터
4. 위치 에너지 방법
각 종류의 연산마다 상각 시간을 할당 ( 회계 방법과 여기까지는 동일 )
- 각 객체에 대한 남는 상각 시간을 저장하지 않음
- 전체 자료구조에 대하여 남는 상각 시간을 위치 에너지처럼 생각하고 저장한다.
-
i번 째 연산의 상각 시간
-
최악 수행 시간의 상한
변형된 스택 연산
ϕ -> 스택에 들어있는 객체의 개수
- ϕ(D0)=0, ϕ(Di)≥0=ϕ(D0)
- 각 연산의 상각 시간
- n개의 연산에 대한 최악의 수행 시간 : O(n)
이진 카운터
ϕ(Di)=bi
- bi: i번째 연산 종료 후 상태 Di에서 값이 1인 비트의 개수
- Increment 연산의 실제 연산 시간 : 최대 ti+1
- 리셋 되는 비트의 개수(ti) + 1로 바꾸는 비트의 연산
- 위치 에너지의 변화량
- ϕ(Di)−ϕ(Di−1)≤(bi−1−ti+1)−bi−1=1−ti
- 상각 시간
- ci^=ci+ϕ(Di)−ϕ(Di−1)≤(ti+1)+(1−ti)=2
- 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] : 들어있는 객체의 수
기존 분석
합계 분석
회계 방법
위치 에너지 방법
-
ϕ(T)=2∗num[T]−size[T]
- 테이블 확장 직후 num[T]=size[T]/2 -> ϕ(T)=0
- 테이블이 꽉찬 경우 num[T]=size[T] -> ϕ(T)=num[T]
-
num0=0, size0=0, ϕ0=0
- i번째 연산에 의해 테이블이 확장되지 않은 경우 : sizei=sizei−1
- ci^=ci+ϕi−ϕi−1=1+(2∗numi−sizei)−(2∗numi−1−sizei−1)=1+(2∗numi−sizei)−(2∗numi−1)−sizei)=3
- i번째 연산에 의해 테이블이 확장되지 않은 경우
- sizei=2∗(numi−1), sizei−1=numi−1=numi−1
- ci^=ci+ϕi−ϕi−1=numi+(2∗numi−sizei)−(2∗numi−1−sizei−1)=numi+(2∗numi−2∗(numi−1))−(2∗numi−1)−(numi−1))=3
-
삽입 연산의 상각 시간 : 3 -> O(n)