Metod för potentialer (amorteringsanalys)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 april 2020; verifiering kräver 1 redigering .

Den potentiella metoden är en av de avskrivningsanalysmetoder som låter dig "jämna ut" effekten av dyra men sällsynta operationer på algoritmens totala beräkningskomplexitet [1] [2] .

Definitioner

I metoden för potentialer introduceras en funktion som länkar datastrukturens tillstånd med något icke-negativt tal. Innebörden av denna funktion är att om är det nuvarande tillståndet för strukturen, så är ett värde som kännetecknar mängden arbete av "dyra" operationer, som redan har "betalts" av billigare operationer, men inte har producerats. Således kan det betraktas som en analog av den potentiella energin som är associerad med ett givet tillstånd [1] [2] . Inledningsvis sätts värdet på potentialfunktionen vanligtvis till noll. $\Phi$ $S$ $\Phi (S)$ $\Phi (S)$

Låt vara en separat operation från serien, vara tillståndet för strukturen före denna operation, och vara efter den. Då är den amorterade komplexiteten för verksamheten $o$ $S_{before}$ $S_{after}$ $o$

T_{\mathrm {amortiserat} }(o)=T_{\mathrm {faktisk} }(o)+\Phi (S_{\mathrm {efter} })-\Phi (S_{\mathrm {före} }).

Förhållandet mellan avskrivet och verkligt värde

Den totala upplupna kostnaden för en operationssekvens är en giltig övre gräns för den verkliga kostnaden för den operationssekvensen.

För en sekvens av operationer kan man definiera: ${\displaystyle O=o_{1},o_{2},\dots ,o_{n))$

Total avskriven tid: $T_{\mathrm {amortiserat} }(O)=\summa _{i=0}^{n}T_{\mathrm {amortiserat} }(o_{i}),$
Total realtid: $T_{\mathrm {faktisk} }(O)=\summa _{i=0}^{n}T_{\mathrm {faktisk} }(o_{i}).$

I dessa beteckningar:

T_{\mathrm {amortiserat} }(O)=\summa _{i=1}^{n}\left(T_{\mathrm {faktisk} }(o_{i})+\Phi (S_{ i})-\Phi (S_{i-1})\right)=T_{\mathrm {faktisk} }(O)+\Phi (S_{n})-\Phi (S_{0}),

Således bildar sekvensen av potentiella funktionsvärden en teleskopisk summa , där successiva initiala och slutliga potentiella funktionsvärden upphäver varandra.

Av det faktum att ojämlikheten följer , som sagts tidigare. $\Phi (S_{0})=0$ $\Phi (S_{n})\geq 0$ $T_{\mathrm {faktisk} }(O)\leq T_{\mathrm {amortiserat} }(O)$

Exempel

Stack med massborttagningar

Du kan överväga en variant av stacken som stöder följande operationer:

initiera - skapa en tom stack.
push - lägg till ett enstaka element i toppen av stapeln, öka dess storlek med . $ett$
pop(k) - ta bort element från toppen av stapeln, där den inte överstiger den aktuella stapelstorleken. $k$ $k$

En operation pop(k) tar tid, medan den totala körtiden kan analyseras med hjälp av följande potentialfunktion lika med antalet element i stacken . Detta värde är alltid icke-negativt, medan push -operationen fungerar för en konstant och ökar med ett, och pop- operationen fungerar för , men minskar också den potentiella funktionen med , så dess amorterade tid är också konstant. Det följer av detta att den totala exekveringstiden för varje sekvens av operationer är lika i värsta fall. $Ok)$ $\Phi (S)$ $S$ $\Phi$ $Ok)$ $k$ $m$ $O(m)$

Binär räknare

Ett annat exempel är en räknare , implementerad som ett binärt tal som stöder följande operationer:

initiera – skapa en räknare med värde . $0$
inc- öka räknarvärdet med . $ett$

För att visa att den amortiserade kostnaden för inc är , överväg en potentiell funktion lika med antalet räknarbitar lika med ( Hamming vikt räknaren). Vid behov är en sådan funktion alltid icke-negativ och är initialt lika med . Inc -operationen inverterar först den minst signifikanta biten i räknaren och sedan, om den var , upprepas samma sak med nästa bit tills den träffar . Om det innan dess fanns enstaka bitar i slutet av räknarens bitpost, kommer det att vara nödvändigt att invertera biten, spendera enheter i realtid och minska potentialen med . Således är den upplupna kostnaden för inc- verksamheten lika och, som en konsekvens, är genomförandetiden för inc- verksamheten lika med . $O(1)$ $ett$ $0$ $ett$ $0$ $k$ $k+1$ $k+1$ $k-1$ $2$ $m$ $O(m)$

Applikationer

Metoden för potentialer används vanligtvis för att analysera Fibonacci-högar , där att extrahera ett element tar amorterad logaritmisk tid, och alla andra operationer tar amorterad konstant tid [3] . Den kan också användas för att visa att ett splayträd har en logaritmisk amorterad driftskostnad [4] .

Anteckningar

↑ 1 2 Goodrich, Michael T. & Tamassia, Roberto (2002), 1.5.1 Amortization Techniques, Algorithm Design: Foundations, Analysis and Internet Examples , Wiley, sid. 36–38 .
↑ 1 2 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 18.3 Potentiell metod // Algoritmer: Konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - S. 412-416. — ISBN 5-8459-0857-4 .
↑ Cormen et al., kapitel 20, "Fibonacci Heaps", sid. 476-497.
↑ Goodrich och Tamassia, avsnitt 3.4, "Splay Trees", s. 185-194.