잠재적 방법이란?
계산 복잡도 이론에서 잠재적 방법(potential method)은 자료구조의 분할 상환(amortized) 시간·공간 복잡도를 분석하기 위해 사용되는 기법입니다. 이 방법은 드물게 발생하지만 비용이 매우 큰 연산의 부담을 전체 연산 시퀀스에 걸쳐 분산시켜, 자료구조가 일련의 연산에 대해 보여주는 전반적인 성능을 평가할 수 있게 해줍니다.
잠재 함수 Φ의 개념
잠재적 방법에서는 자료구조의 상태를 음수가 아닌 숫자로 변환하는 함수 Φ(파이)를 선택합니다. S를 자료구조의 한 상태라고 할 때, Φ(S)는 분할 상환 분석에서 미리 계상되었지만 아직 수행되지 않은 작업량을 의미합니다.
비유하자면, Φ(S)는 해당 상태에 저장된 위치 에너지의 양을 계산하는 것과 같습니다. 자료구조를 초기화하기 전에는 잠재 값이 0으로 정의됩니다. 또는 Φ(S)를 상태 S의 무질서한 정도, 혹은 이상적인 상태로부터 얼마나 떨어져 있는지를 나타내는 척도로 생각할 수도 있습니다.
예제: 잠재 함수가 만족해야 하는 두 가지 조건
자료구조의 상태들에 대해 정의된 잠재 함수 Φ가 다음 두 속성을 만족한다고 가정해 보겠습니다.
- Φ(a₀) = 0 — 여기서 a₀는 자료구조의 초기(시작) 상태입니다.
- Φ(aₜ) ≥ 0 — 계산 과정에서 발생하는 자료구조의 모든 상태 aₜ에 대해 잠재 값은 항상 0 이상이어야 합니다.
직관적으로 잠재 함수는 계산의 어느 시점에서든 미리 충전된 시간(precharged time)을 추적하는 역할을 합니다. 즉, 비용이 큰 연산을 지불하기 위해 미리 저축해 둘 수 있는 시간의 양을 측정합니다. 이는 은행원 방법(banker's method)의 은행 잔고와 유사하지만, 흥미로운 점은 잠재 함수가 그 상태에 도달하게 된 계산의 이력과는 무관하게 오직 자료구조의 현재 상태에만 의존한다는 것입니다.
분할 상환 시간의 정의
연산의 분할 상환 시간(amortized time)은 다음과 같이 정의됩니다.
c + Φ(a′) − Φ(a)
여기서 c는 해당 연산의 실제 비용이며, a와 a′는 각각 연산 이전과 이후의 자료구조 상태를 나타냅니다. 즉, 분할 상환 시간 = 실제 시간 + 잠재 변화량입니다.
이상적으로는 각 연산의 분할 상환 시간이 작아지도록 Φ를 설계해야 합니다. 이를 위해 잠재 변화량은 저비용 연산에서는 양수로, 고비용 연산에서는 음수로 측정되어야 합니다. 그렇게 하면 저비용 연산이 미리 '저축'한 잠재 에너지가 고비용 연산이 실행될 때 소모되면서, 전체 비용이 개별 연산에 균등하게 분배되는 효과를 얻을 수 있습니다.