전위법

계산 복잡성 이론에서, 잠재적 방법은 데이터 구조의 상각된 시간과 공간 복잡성을 분석하기 위해 사용되는 방법이며, 드물지만 비용이 많이 드는 운영 비용을 부드럽게 하는 일련의 운영보다 그 성능을 측정하는 방법이다.^[1][2]

상각시간의 정의

잠재적 방법에서는 데이터 구조 상태를 음수가 아닌 숫자에 매핑하는 function 함수를 선택한다.S가 데이터 구조의 상태라면, φ(S)은 상각된 분석에서 회계처리되었지만 아직 수행되지 않은 작업을 나타낸다.따라서 φ(S)은 해당 상태에 저장된 잠재적 에너지의 양을 계산하는 것으로 생각할 수 있다.^[1][2]데이터 구조를 초기화하기 전의 잠재적 값은 0으로 정의된다.대안적으로 ((S)은 상태 S의 무질서의 양 또는 이상 상태와의 거리를 나타내는 것으로 생각할 수 있다.

o는 일부 데이터 구조에 대한 일련의 운영 내에서 개별적인 운영이 되도록 하고, S는_before o 작동 이전의 데이터 구조 상태를 나타내고, S는_after o가 완료된 후 그것의 상태를 나타낸다.일단 φ을 선택했으면, o 운용에 대한 상각시간은 다음과 같이 정의된다.

${\displaystyle T_{\mathrm {amortified} }(o)=T_{\mathrm {actual} }(o)+C\cdot(\Phi(S_{\mathrm {after})-\Phi(S_{\mathrm {before}),}$

여기서 C는 (시간 단위) 비례의 음수가 아닌 상수로, 분석 내내 고정되어 있어야 한다.즉, 상각시간은 운전에서 실제 소요된 시간과 운전으로 인한 잠재적 차이의 C배로 정의된다.^[1][2]

큰 O 표기법을 이용한 점근법적 계산 복잡성을 연구할 때 상수 인자는 무관하므로 상수 C는 대개 생략한다.

상각된 시간과 실제 시간의 관계

인위적인 외관에도 불구하고 일련의 운영 과정의 총 상각 시간은 동일한 운영 순서에 대한 실제 시간에 유효한 상한을 제공한다.

$작업{\displaystyle }$ O${\displaystyle }$=${\displaystyle {}_{}{o\mathrm{}}_{}}$ 1, ${\displaystyle {o\mathrm{}}_{}}$2 …${\displaystyle }$, ${\displaystyle o_{}}$ n$${\$displaystyle O=o_{1}, o_{2},\dots, o_{n$},$$정의:

• 총 상각 시간:${\displaystyle T_{\mathrm {amortified}} }=\sum _{i=1}^{n$$}}T_{\mathrm {amortified} }(o_{i}),}$
• 총 실제 시간:$displaystyle$$}}T_{\mathrm {actual} }(o_{i}).$$}$

다음:

${\displaystyle T_{\mathrm {amortified} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {actual})(o_{i})+C\cdot(\Phi(S_{i}-\Phi(S_{i-1})\오른쪽)=T_{{\mathrm {actual} }(O)+C\cdot(\Phi(S_{n}-\Phi(S_{0}),}$

여기서 잠재적 함수 값의 순서는 초기 및 최종 잠재적 함수 값 이외의 모든 용어가 쌍으로 취소되는 텔레스코핑 시리즈를 형성한다.이를 재정비하여 다음과 같은 이점을 얻을 수 있다.

${\displaystyle T_{\mathrm {actual} }(O)=T_{\mathrm {amortified} }(O)-C\cdot(\Phi(S_{n}-\Phi(S_{0}))}$

Since ${\displaystyle \Phi (S_{0})=0}$ and ${\displaystyle \Phi (S_{n})\geq 0}$, ${\displaystyle T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortized} }(O)}$, so the amortized time can be used to provide an accurate upper bound on the act개별 영업에 대해 상각된 시간은 실제 영업 시간과 크게 다를 수 있지만 일련의 영업 순서의 ual 시간.

최악의 경우 투입변수에 대한 상각해석

일반적으로 상각된 분석은 입력 순서에 대한 최악의 가정과 함께 사용된다.이러한 가정 하에, X가 데이터 구조에 의해 수행될 수 있는 운영 유형이고 n이 주어진 데이터 구조의 크기(예: 포함된 항목의 수)를 정의하는 정수라면, X 타입의 운영에 대한 상각 시간은 데이터 스트루에서 가능한 모든 작업 순서 중에서 최대값으로 정의된다.크기 n과 유형 X의 모든 운영 o의_i 염기서열, 운영 o의_i 상각 시간 o.

이 정의에서 일련의 작업을 수행하는 시간은 각 운영 유형에 대한 상각된 시간에 해당 유형의 운영 횟수를 곱하여 추정할 수 있다.

예

동적 배열

동적 배열은 항목 배열을 유지하기 위한 데이터 구조로, 배열 내의 위치에 무작위 액세스와 배열 크기를 하나씩 증가시키는 기능을 모두 허용한다.Java에서는 "ArrayList" 타입으로, Python에서는 "list" 타입으로 이용할 수 있다.

동적 배열은 지금까지 사용된 배열 내의 위치를 나타내는 숫자 n ≤ N과 일정 길이의 N 항목의 배열 A로 구성된 데이터 구조로 구현될 수 있다.이 구조로 동적 어레이에 대한 무작위 액세스는 내부 어레이 A의 동일한 셀에 접속하여 실행할 수 있으며, n < N이 되면 동적 어레이 크기를 증가시키는 연산은 단순히 n을 증가시켜 실행할 수 있다.단, n = N일 때는 A의 크기를 조정할 필요가 있으며, 일반적인 전략은 A의 크기를 두 배로 늘려 길이 2n의 새로운 배열로 A를 대체하는 것이다.^[3]

이 구조는 잠재적 기능을 사용하여 분석할 수 있다.

φ = 2n - N

크기 조정 전략은 항상 A가 적어도 절반은 차게 하기 때문에, 이 잠재적 기능은 원하는 대로 항상 음성이 아니다.

증가 크기 연산이 크기 조정 연산으로 이어지지 않을 경우 φ은 상수인 2만큼 증가한다.따라서, 운용의 지속적인 실제 시간과 전위의 지속적인 증가가 결합되어 이러한 유형의 운용에 대한 상각 시간을 일정하게 제공한다.

그러나, 증가 크기 연산이 크기 조정을 일으키면, 크기 조정 후 φ의 잠재적 값은 0으로 감소한다.새로운 내부 배열 A를 할당하고 이전 내부 배열에서 새 내부 배열로 모든 값을 복사하는 데는 실제 시간이 O(n)가 걸리지만, (비례성 C의 상수를 적절히 선택하면) 이것은 잠재적 기능의 감소에 의해 완전히 취소되어 다시 운영에 대한 일정한 총 상각 시간이 남게 된다.

데이터 구조의 다른 작업(배열 크기를 변경하지 않고 배열 셀을 읽고 쓰는 작업)은 잠재적 기능을 변화시키지 않으며 실제 시간과 동일한 상각 시간을 갖는다.^[2]

따라서 이러한 크기 조정 전략과 잠재적 기능의 선택으로, 잠재적 방법은 모든 동적 배열 운영이 상각된 시간을 일정하게 소모한다는 것을 보여준다.이를 운영 순서에 대한 상각된 시간과 실제 시간과 관련된 불평등과 결합하면, 일부 개별 운영 자체가 선형적인 시간이 소요될 수 있음에도 불구하고 최악의 경우 n개의 동적 배열 운영 순서가 실제 시간을 소요한다는 것을 알 수 있다.^[2]

동적 어레이에 어레이 크기를 줄이고 크기를 늘리는 작업이 포함된 경우, 잠재적인 기능이 음수가 되지 않도록 수정해야 한다.이를 위한 한 가지 방법은 Ⅱ에 대한 위의 공식을 절대값으로 대체하는 것이다.

멀티팝 스택

다음 작업을 지원하는 스택을 고려하십시오.

• 초기화 - 빈 스택을 생성하십시오.
• 밀어넣기 - 스택 위에 단일 요소를 추가하여 스택을 1만큼 확장하십시오.
• Pop(k) - 스택의 상단에서 k 요소 제거(k가 현재 스택 크기 이하임)

팝(k)에는 O(k) 시간이 필요하지만, 우리는 모든 작업이 O(1) 상각된 시간이 걸린다는 것을 보여주고 싶다.

이 구조는 잠재적 기능을 사용하여 분석할 수 있다.

φ = 스택 내 요소 수

이 숫자는 필요에 따라 항상 음수가 아니다.

푸시 연산은 일정한 시간이 걸리고 φ이 1 증가하므로 상각된 시간은 일정하다.

Pop 연산에는 O(k) 시간이 걸리지만 φ도 k만큼 감소하므로 상각된 시간도 일정하다.

이것은 최악의 경우 M 연산의 모든 순서가 O(m) 실제 시간을 소모한다는 것을 증명한다.

이진 계수기

이진수로 표현되고 다음 작업을 지원하는 카운터를 고려하십시오.

• Initialize: 값이 0인 카운터를 생성하십시오.
• Inc: 카운터에 1을 추가하십시오.
• 읽기: 현재 카운터 값을 반환하십시오.

이 예에서, 우리는 transdicotomous machine 모델을 사용하지 않고, 대신 증분에서 비트당 1개의 시간 단위가 필요하다.우리는 Inc.가 O(1)의 상각 시간을 소요한다는 것을 보여주고 싶다.

이 구조는 잠재적 기능을 사용하여 분석할 수 있다.

φ = 비트 수 대 1 = 해밍가중치(카운터)

이 숫자는 항상 음수가 아니며 필요에 따라 0으로 시작한다.

Inc 수술은 가장 중요도가 낮은 비트를 뒤집는다.그런 다음 LSB가 1에서 0으로 플립된 경우 다음 비트도 플립된다.이것은 마침내 0에서 1로 약간 뒤집힐 때까지 계속되며, 그 때 플립이 멈춘다.카운터가 처음에 k 1비트로 끝나면 총 k+1비트를 뒤집어서 실제 시간 k+1이 걸리고 잠재력이 k-1이 줄어들기 때문에 상각된 시간은 2가 된다.따라서 m Inc를 운영하는 실제 시간은 O(m)이다.

적용들

잠재적 함수 방법은 일반적으로 항목 제거 시 로그 상각 시간이 소요되고 다른 모든 작업은 일정한 상각 시간이 걸리는 우선순위 대기열의 한 형태인 피보나치 힙을 분석하는 데 사용된다.^[4]또한 운영당 로그 상각 시간을 갖는 바이너리 검색 트리의 자체 조정 형태인 splay 트리를 분석하는 데도 사용할 수 있다.^[5]

참조