융합 연산 상각 비용 계산의 어려움
융합(meld) 연산의 상각 비용(amortized cost)을 계산하는 것은 결코 쉬운 작업이 아닙니다. 가장 큰 어려움은 무작위 연산 시퀀스에서 서로 다른 지점에서 수행되는 연산의 비용이 크게 달라지기 때문에, 이 변동을 누적하여 분석해야 한다는 점입니다.
물론 설계 목표는 일련의 연산 시퀀스 전체 비용에 영향을 받습니다. 그러나 개별 연산의 상각 비용을 단순히 연산 시퀀스의 비용 관점에서 정의하는 것은 아무런 성과도 가져다주지 않습니다. 이러한 상황을 효과적으로 처리하는 가장 좋은 방법은 잠재 함수(potential function)를 도입하여 실제 비용의 변동을 상쇄하는 것입니다.
상각 비용의 정의
먼저 몇 가지 용어를 정의하겠습니다.
- B: 기본 연산 P = {P1, P2, …, Pk}를 갖는 추상 자료형(ADT, Abstract Data Type)
- DS: B를 구현하는 자료구조
- F: 자료구조의 각 구성(configuration)을 음이 아닌 실수로 대응시키는 잠재 함수. 단, 초기 상태에 대해 F(Φ) = 0으로 가정합니다.
- DSj: 구성 DS에 대해 연산 Pk를 수행했을 때 얻어지는 새로운 구성
- C: 구성 DS에 대해 Pk를 수행하는 데 드는 실제 비용(actual cost)
이때 구성 DS에 대한 연산 Pk의 상각 비용 a(Pk, DS)는 다음 공식으로 정의됩니다.
a(Pk, DS) = C + F(DSj) − F(DS)
즉, 상각 비용은 실제 비용에 잠재 함수 값의 변화량을 더한 값입니다. 잠재 함수는 연산 직전과 직후의 자료구조 상태 차이를 반영함으로써, 특정 연산에서 발생하는 비용의 급격한 변동을 평탄하게 만들어 줍니다.
상각 비용의 점근적 분석
크기가 m인 모든 구성 DS에 대해 다음 조건이 성립한다고 가정해 봅시다.
a(Pk, DS) ≤ c·g(m)
여기서 c는 상수입니다. 이 조건이 만족되면, 우리는 연산 Pk의 상각 비용이 O(g(m))라고 결론 내릴 수 있습니다. 이처럼 잠재 함수를 활용하면 개별 연산의 비용 변동에 흔들리지 않고, 연산 시퀀스 전체의 성능을 안정적으로 분석할 수 있습니다.