5. Amortized Analysis and Adversary Argument

들어가기에 앞서서 stack의 time complexity를 분석해 봅시다. 3가지 operation이 있고 각각의 시간 복잡도는 다음과 같이 소요됩니다.

Push	Pop	Multipop(k)
O(1)	O(1)	O(min(k,s)) = O(n) worst case

 

Worst-case analysis

$n×O(n) = O(n^2)$

 

Probabilistic analysis

각각의 operation이 차지하는 비율이 ${n \over 3}$이라고 생각해 볼 수 있습니다. 따라서 시간 복잡도는 다음과 같습니다.

 

$T(A) = {n \over 3}O(1) + {n \over 3}O(1) + {n \over 3}O(n) = O(n^2)$

 

Amortized Analysis

기존처럼 하나의 operation이 아니라 sequence of operations을 보고 알고리즘의 복잡도를 분석하는 방법입니다. 각 operation은 average cost를 가지며, 알고리즘의 성능은 worst case에 보장됩니다. 가능한 모든 Input에 대해 분석을 실행했던 Probabilistic analysis와 다른 분석 방법입니다.

 

Aggregate analysis

Average cost를 ${total-cost-of-n-operations \over n}$으로 구하는 방법입니다.

 

Stack에서 Push와 Pop(+Multipop(k))의 관계에 대해서 생각해 봅시다. Pop의 경우, Push가 이루어진 횟수 내에 바운드되는 것을 알 수 있습니다. K push가 이루어져야 K만큼의 pop을 실행할 수 있기 때문입니다.

 

따라서 Push의 average cost를 구해보면, ${O(n) \over n}$이기 때문에, $O(1)$의 cost가 드는 것을 알 수 있습니다.

 

•  Push $O(1)$
•  Pop $O(1)$
•  Multipop $O(1)$

 

따라서 알고리즘의 시간 복잡도는 $O(1)×n = O(n)$임을 알 수 있습니다.

 

Accounting Method

실제 비용 대신에 amortized cost로 계산하는 방법입니다. Amortized cost는 실제 cost에 upper bound이기 때문에 사용가능한 방법입니다. 표를 그려보면 이해가 쉽습니다.

	Actual cost	Amortized cost
Push	1	2
Pop	1	0 (already paid by Push)
Multipop(k)	min(k,s)	0 (already paid by Push)

 

Push에 대한 cost만 생각하여 시간 복잡도를 구해보면, $O(1)×n = O(n)$임을 알 수 있습니다.

 

Potential Method

Operation을 고려하기보다는 전체 데이터 구조의 potential energy를 고려합니다. Potential energy는 우리가 operation을 수행하는 경우에만 변한다는 것이 핵심입니다.

 

Amortized cost = $c_i+ \Phi(D_i) - \Phi(D_{i-1})$

 

Stack에 대해 사용해봅시다. Stack의 potential energy는 스택에 있는 object의 수와 같습니다. 따라서 $\Phi(D_0)=0$이고 $\Phi (D_i)≥0$임을 알 수 있습니다. Operation에 따른 amortized cost, $\Phi(D)$를 구해봅시다.

 

• Push
  $c_i' = 1+\Phi(D_i)-\Phi(D_{i-1}) = 2$
• Pop
  $c_i' = 1+\Phi(D_i)-\Phi(D_{i-1}) = 0$
• Multipop
  $c_i' = min(k,s) + \Phi(D_i)-\Phi(D_{i-1}) = 0$

 

따라서 Push에 대한 cost만 생각하여 시간 복잡도를 구해보면, $O(1)×n = O(n)$임을 알 수 있습니다. Total amortized cost가 total actual cost의 upper bound이기 때문에, worst case에 대한 비용도 $O(n)$임을 알 수 있습니다. 

 

Adversary argument

증명 방법중 하나입니다. 강력한 공격자는 알고리즘의 worst case 시나리오를 야기하는 Input을 결정하려고 하며, 알고리즘의 response가 일정한 값을 줄 때까지 input을 생성해 냅니다.