Metoda potențialelor (analiza de amortizare)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 7 aprilie 2020; verificarea necesită 1 editare .

Metoda potențială este una dintre metodele de analiză a deprecierii care vă permite să „neteziți” impactul operațiilor costisitoare, dar rare, asupra complexității totale de calcul a algoritmului [1] [2] .

Definiții

În metoda potențialelor, este introdusă o funcție care leagă starea structurii de date cu un număr nenegativ. Semnificația acestei funcții este că, dacă este starea actuală a structurii, atunci este o valoare care caracterizează cantitatea de muncă a operațiunilor „scumpe”, care a fost deja „plătită” de operațiuni mai ieftine, dar nu a fost produsă. Astfel, poate fi considerată ca un analog al energiei potențiale asociate cu o stare dată [1] [2] . Inițial, valoarea funcției potențiale este de obicei setată la zero. $\Phi$ $S$ $\Phi (S)$ $\Phi (S)$

Să fie o operație separată de serie, să fie starea structurii înainte de această operație și să fie după ea. Atunci complexitatea amortizată a operațiunii este $o$ $S_{inainte}$ $S_{după}$ $o$

T_{\mathrm {amortizat} }(o)=T_{\mathrm {actual} }(o)+\Phi (S_{\mathrm {după}})-\Phi (S_{\mathrm {înainte} }).

Relația dintre valoarea amortizată și valoarea reală

Costul total amortizat al unei secvențe de operațiuni este o limită superioară valabilă pentru costul real al acelei secvențe de operațiuni.

Pentru o secvență de operații , se poate defini: $O=o_{1},o_{2},\dots,o_{n)$

Timp total amortizat: $T_{\mathrm {amortizat} }(O)=\sum _{i=0}^{n}T_{\mathrm {amortizat} }(o_{i}),$
Timp real total: $T_{\mathrm {actual} }(O)=\sum _{i=0}^{n}T_{\mathrm {actual} }(o_{i}).$

În aceste notații:

T_{\mathrm {amortizat} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {actual}}(o_{i})+\Phi (S_{ i})-\Phi (S_{i-1})\right)=T_{\mathrm {actual} }(O)+\Phi (S_{n})-\Phi (S_{0}),

Astfel, succesiunea valorilor funcției potențiale formează o sumă telescopică , în care valorile succesive ale funcției potențiale inițiale și finale se anulează reciproc.

Din faptul că inegalitatea decurge , așa cum sa spus mai devreme. $\Phi (S_{0})=0$ $\Phi (S_{n})\geq 0$ $T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortizat} }(O)$

Exemple

Stiva cu eliminări în masă

Puteți lua în considerare o variantă a stivei care acceptă următoarele operații:

initialize - creați o stivă goală.
push - adăugați un singur element în partea de sus a stivei, mărindu-i dimensiunea cu . $unu$
pop(k) - elimina elementele din partea de sus a stivei, unde nu depășește dimensiunea actuală a stivei. $k$ $k$

O operație pop(k) necesită timp, în timp ce timpul total de rulare poate fi analizat folosind următoarea funcție potențială egală cu numărul de elemente din stiva . Această valoare este întotdeauna nenegativă, în timp ce operația push funcționează pentru o constantă și crește cu unu, iar operația pop funcționează pentru , dar scade și funcția potențială cu , astfel încât timpul său amortizat este și el constant. De aici rezultă că timpul total de execuție al oricărei secvențe de operații este egal în cel mai rău caz. $O.K)$ $\Phi (S)$ $S$ $\Phi$ $O.K)$ $k$ $m$ $O(m)$

Contor binar

Un alt exemplu este un numărător , implementat ca număr binar care acceptă următoarele operații:

initialize -- creeaza un contor cu valoare . $0$
inc - incrementează valoarea contorului cu . $unu$

Pentru a arăta că costul amortizat al inc este , luăm în considerare o funcție potențială egală cu numărul de biți de contor egal cu ( Greutatea Hamming contorului). După cum este necesar, o astfel de funcție este întotdeauna nenegativă și este inițial egală cu . Operația inc inversează mai întâi bitul cel mai puțin semnificativ al contorului și apoi, dacă a fost , repetă același lucru cu următorul bit până când atinge . Dacă înainte de aceasta existau biți unici la sfârșitul înregistrării de biți a contorului, va fi necesar să se inverseze bitul, cheltuind unități de timp real și reducând potențialul cu . Astfel, costul amortizat al operațiunii inc este egal și, în consecință, timpul de execuție al operațiunilor inc este egal cu . $O(1)$ $unu$ $0$ $unu$ $0$ $k$ $k+1$ $k+1$ $k-1$ $2$ $m$ $O(m)$

Aplicații

Metoda potențialelor este folosită în mod obișnuit pentru a analiza grămezi Fibonacci , unde extragerea unui element necesită timp logaritmic amortizat, iar toate celelalte operațiuni iau timp constant amortizat [3] . Poate fi folosit și pentru a arăta că un arbore splay are un cost amortizat logaritmic al operațiunilor [4] .

Note

↑ 1 2 Goodrich, Michael T. & Tamassia, Roberto (2002), 1.5.1 Amortization Techniques, Algorithm Design: Foundations, Analysis and Internet Examples , Wiley, p. 36–38 .
↑ 1 2 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 18.3 Potential Method // Algorithms: Construction and Analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - S. 412-416. — ISBN 5-8459-0857-4 .
↑ Cormen și colab., Capitolul 20, „Goldurile Fibonacci”, pp. 476-497.
↑ Goodrich și Tamassia, Secțiunea 3.4, „Splay Trees”, pp. 185-194.