용융 작업의 상각 비용을 계산하는 것은 어려운 작업입니다. 주요 어려움은 무작위 작업 순서의 여러 지점에서 수행되는 작업 비용의 광범위한 변동을 누적하는 것입니다. 우리의 설계 목표가 일련의 작업 비용에 영향을 받지만 작업 시퀀스 비용의 관점에서 작업의 상각된 비용 개념을 정의하는 것은 아무 소용이 없습니다. 실제 비용의 변동을 설정하는 잠재적 기능을 구현하는 것은 상황을 처리하는 완벽한 방법입니다. 다음 주제에서는 상각 비용의 개념에 대해 논의합니다.
B를 기본 연산 P ={P1을 사용하는 추상 데이터 유형(ADT)이라고 합시다. , P2 ,……, Pk } 그리고 DS를 B를 구현하는 데이터 구조라고 하자. F를 음이 아닌 실수로 데이터 구조의 구성에 지정된 잠재적 함수라고 하자. F(Φ) =0이라고 합시다. DS j 구성 DS에 대해 Pk 작업을 수행하는 경우 얻는 구성을 지정하고 C가 DS에서 Pk를 수행하는 실제 비용을 나타내도록 합니다.
그런 다음 a(Pk, DS)로 표시된 DS에서 작동하는 Pk의 상각 상각 비용은 다음과 같이 표시됩니다.
a(Pk , DS) =C + F(DS j ) – F(DS)
만약 a(Pk , DS)≤ cjg(m) 크기가 m인 모든 구성 DS에 대해 Pk의 상각 상각 비용이 O(g(m))이라는 결론을 내립니다.