계산 복잡성 이론에 따르면 잠재적인 방법은 데이터 구조의 상각된 시간 및 공간 복잡성을 분석하기 위해 구현된 방법으로 정의되며, 이는 드물지만 값비싼 작업의 비용을 제거하는 일련의 작업에 대한 성능 척도입니다.
잠재적인 방법에서는 데이터 구조의 상태를 음수가 아닌 숫자로 변환하는 함수 Φ가 선택됩니다. S가 자료구조의 상태로 취급된다면, Φ(S)는 상각분석에서 계상되었으나 아직 수행되지 않은 작업을 의미한다. 따라서 Φ(S)는 해당 상태에 저장된 위치 에너지의 양을 계산하는 것으로 상상할 수 있습니다. 데이터 구조를 초기화하기 전에 잠재적인 값은 0으로 정의됩니다. 또는 Φ(S)는 상태 S의 무질서의 정도 또는 이상적인 상태로부터의 거리를 나타내는 것으로 상상할 수 있습니다.
예시
데이터 구조의 상태에서 잠재적인 함수 Φ("Phi"로 읽음)를 나타낼 수 있습니다. 다음 속성을 충족합니다. -
- Φ(a0) =0, 여기서 a0은 데이터 구조의 시작 상태입니다.
- Φ(at) ≥ 0은 계산 과정에서 발생하는 데이터 구조의 모든 상태 at에 대한 것입니다.
직관적으로, 잠재적 기능은 계산의 어느 시점에서든 사전 충전된 시간을 추적할 수 있습니다. 비용이 많이 드는 작업에 대해 지불할 수 있는 절약된 시간의 양을 측정합니다. 은행가 방식의 은행 잔고와 같습니다. 그러나 흥미롭게도 이는 데이터 구조의 현재 상태에만 의존하며, 그 상태가 된 계산 이력이 무엇이든 상관없습니다.
그런 다음 작업의 상각 시간을 다음과 같이 정의합니다.
c + Φ(a') − Φ(a),
여기서 c는 연산의 원래 비용이고, a'는 연산 전후의 데이터 구조 상태입니다. 따라서 상각된 시간은 실제 시간에 잠재적인 변화를 더한 것으로 정의됩니다. 이상적으로는 각 작업의 상각 시간이 작아지도록 Φ를 정의해야 합니다. 따라서 잠재력의 변화는 저비용 작업의 경우 양수, 고비용 작업의 경우 음수로 측정해야 합니다.