Metoda potențială - Potential method

În teoria complexității de calcul , metoda potențială este o metodă utilizată pentru a analiza complexitatea de timp și spațiu amortizată a unei structuri de date , o măsură a performanței sale pe secvențe de operații care netezește costul operațiilor rare, dar costisitoare.

Definiția amortized time

În metoda potențială, se alege o funcție Φ care mapează stările structurii datelor la numere non-negative. Dacă S este o stare a structurii datelor, Φ ( S ) reprezintă lucrarea care a fost contabilizată („plătită”) în analiza amortizată, dar care nu a fost încă efectuată. Astfel, Φ ( S ) poate fi considerat a calcula cantitatea de energie potențială stocată în acea stare. Valoarea potențială înainte de operația de inițializare a unei structuri de date este definită ca fiind zero. Alternativ, Φ ( S ) poate fi considerat a reprezenta cantitatea de tulburare în starea S sau distanța sa de o stare ideală.

Fie o orice operație individuală dintr-o secvență de operații pe o anumită structură de date, cu S _{înainte de a} indica starea structurii de date înainte de operația o și S _după ce a indicat starea acesteia după ce operațiunea o a fost finalizată. Odată ales Φ, timpul amortizat pentru operațiunea o este definit ca fiind

${\ displaystyle T _ {\ mathrm {amortized}} (o) = T _ {\ mathrm {actual}} (o) + C \ cdot (\ Phi (S _ {\ mathrm {after}}) - \ Phi (S _ {\ mathrm {înainte}}))),}$

unde C este o constantă de proporționalitate non-negativă (în unități de timp) care trebuie să rămână fixă ​​pe tot parcursul analizei. Adică, timpul amortizat este definit pentru a fi timpul efectiv luat de operațiune plus C de diferența de potențial cauzată de operațiune.

Atunci când se studiază complexitatea de calcul asimptotică folosind notația O mare , factorii constanți sunt irelevanți și deci constanta C este de obicei omisă.

Relația dintre timpul amortizat și timpul efectiv

În ciuda aspectului său artificial, timpul total amortizat al unei secvențe de operații oferă o limită superioară valabilă la timpul real pentru aceeași secvență de operații.

Pentru orice succesiune de operații , definiți: ${\ displaystyle O = o_ {1}, o_ {2}, \ dots, o_ {n}}$

• Timpul total amortizat: ${\ displaystyle T _ {\ mathrm {amortized}} (O) = \ sum _ {i = 1} ^ {n} T _ {\ mathrm {amortized}} (o_ {i}),}$
• Timpul real total: ${\ displaystyle T _ {\ mathrm {actual}} (O) = \ sum _ {i = 1} ^ {n} T _ {\ mathrm {actual}} (o_ {i}).}$

Atunci:

${\ displaystyle T _ {\ mathrm {amortized}} (O) = \ sum _ {i = 1} ^ {n} \ left (T _ {\ mathrm {actual}} (o_ {i}) + C \ cdot (\ Phi (S_ {i}) - \ Phi (S_ {i-1})) \ right) = T _ {\ mathrm {actual}} (O) + C \ cdot (\ Phi (S_ {n}) - \ Phi (S_ {0})),}$

unde secvența valorilor funcției potențiale formează o serie telescopică în care toți termenii, cu excepția valorilor funcției potențiale inițiale și finale, se anulează în perechi. Reamenajând acest lucru, obținem:

${\ displaystyle T _ {\ mathrm {actual}} (O) = T _ {\ mathrm {amortizat}} (O) -C \ cdot (\ Phi (S_ {n}) - \ Phi (S_ {0})). }$

Întrucât și ,, deci timpul amortizat poate fi utilizat pentru a furniza o limită superioară exactă asupra timpului real al unei secvențe de operații, chiar dacă timpul amortizat pentru o operațiune individuală poate varia foarte mult față de timpul său real. ${\ displaystyle \ Phi (S_ {0}) = 0}$${\ displaystyle \ Phi (S_ {n}) \ geq 0}$${\ displaystyle T _ {\ mathrm {actual}} (O) \ leq T _ {\ mathrm {amortizat}} (O)}$

Analiza amortizată a celor mai nefavorabile intrări

De obicei, analiza amortizată este utilizată în combinație cu o ipoteză în cel mai rău caz despre secvența de intrare. Cu această ipoteză, dacă X este un tip de operație care poate fi efectuat de structura de date, iar n este un număr întreg care definește dimensiunea structurii de date date (de exemplu, numărul de articole pe care le conține), atunci timpul amortizat pentru operațiile de tip X este definit ca fiind maximul, dintre toate secvențele posibile de operații pe structuri de date de dimensiunea n și toate operațiunile o _i de tip X în cadrul secvenței, a timpului amortizat pentru operația o _i .

Cu această definiție, timpul pentru efectuarea unei secvențe de operații poate fi estimat prin înmulțirea timpului amortizat pentru fiecare tip de operație din secvență cu numărul de operații de acel tip.

Exemple

Matrice dinamică

O matrice dinamică este o structură de date pentru menținerea unei matrice de articole, permițând atât accesul aleator la pozițiile din matrice, cât și capacitatea de a crește dimensiunea matricei cu una. Este disponibil în Java ca tip "ArrayList" și în Python ca tip "listă".

O matrice dinamică poate fi implementată de o structură de date constând dintr-o matrice A de articole, de o anumită lungime N , împreună cu un număr n  ≤  N care reprezintă pozițiile din matrice care au fost utilizate până acum. Cu această structură, accesele aleatoare la matricea dinamică pot fi implementate accesând aceeași celulă a matricei interne A , iar când n  <  N o operație care mărește dimensiunea matricei dinamice poate fi implementată pur și simplu prin incrementarea  n . Cu toate acestea, atunci când n  =  N , este necesară redimensionarea A , iar o strategie comună pentru aceasta este de a dubla dimensiunea sa, înlocuind A cu o nouă matrice de lungime 2 n .

Această structură poate fi analizată folosind funcția potențială:

Φ = 2 n  -  N

Deoarece strategia de redimensionare face ca A să fie cel puțin pe jumătate, această funcție potențială este întotdeauna non-negativă, după cum se dorește.

Când o operație de mărire nu duce la o operațiune de redimensionare, Φ crește cu 2, o constantă. Prin urmare, timpul efectiv constant al operației și creșterea constantă a potențialului se combină pentru a da un timp amortizat constant pentru o operație de acest tip.

Cu toate acestea, atunci când o operațiune de mărire a mărimii determină o redimensionare, valoarea potențială a lui n scade la zero după redimensionare. Alocarea unei noi matrice interne A și copierea tuturor valorilor din matricea internă veche la cea nouă necesită O ( n ) timp efectiv, dar (cu o alegere adecvată a constantei de proporționalitate C ) aceasta este anulată în totalitate prin scăderea funcția potențială, lăsând din nou un timp total constant amortizat pentru operație.

Celelalte operații ale structurii datelor (citirea și scrierea celulelor matricei fără modificarea dimensiunii matricei) nu determină modificarea funcției potențiale și au același timp constant amortizat ca timpul lor real.

Prin urmare, cu această alegere a strategiei de redimensionare și a funcției potențiale, metoda potențială arată că toate operațiunile din matrice dinamică necesită timp amortizat constant. Combinând acest lucru cu inegalitatea în ceea ce privește timpul amortizat și timpul efectiv pe secvențe de operații, aceasta arată că orice secvență de n operații din matrice dinamică ia O ( n ) timp real în cel mai rău caz, în ciuda faptului că unele dintre operațiunile individuale pot lua ele însele o cantitate liniară de timp.

Când matricea dinamică include operații care scad dimensiunea matricei, precum și creșterea acesteia, funcția potențială trebuie modificată pentru a împiedica să devină negativă. O modalitate de a face acest lucru este înlocuirea formulei de mai sus pentru Φ cu valoarea sa absolută .

Multi-Pop Stack

Luați în considerare o stivă care acceptă următoarele operații:

• Inițializare - creați o stivă goală.
• Împingeți - adăugați un singur element deasupra stivei, mărind stiva cu 1.
• Pop ( k ) - eliminați k elemente din partea de sus a stivei, unde k nu depășește dimensiunea curentă a stivei

Pop ( k ) necesită timp O ( k ), dar dorim să arătăm că toate operațiunile necesită O (1) timp amortizat.

Această structură poate fi analizată folosind funcția potențială:

Φ = numărul-de-elemente-în-stivă

Acest număr este întotdeauna negativ, după cum este necesar.

O operațiune Push necesită timp constant și crește Φ cu 1, deci timpul său amortizat este constant.

O operație Pop necesită timp O ( k ), dar reduce și Φ cu k , deci timpul său amortizat este, de asemenea, constant.

Aceasta demonstrează că orice succesiune de m operații necesită O ( m ) timp real în cel mai rău caz.

Contor binar

Luați în considerare un contor reprezentat ca un număr binar și care susține următoarele operații:

• Inițializare: creați un contor cu valoarea 0.
• Inc: adăugați 1 la tejghea.
• Citire: returnează valoarea contorului curent.

Pentru acest exemplu, nu folosim modelul de mașină transdichotomică , ci în schimb necesită o unitate de timp pentru fiecare operație de biți în increment. Dorim să arătăm că Inc necesită O (1) timp amortizat.

Această structură poate fi analizată folosind funcția potențială:

Φ = număr-de-biți-egal-1 = greutate (contra)

Acest număr este întotdeauna negativ și începe cu 0, după cum este necesar.

O operație Inc întoarce bitul cel mai puțin semnificativ . Apoi, dacă LSB a fost răsturnat de la 1 la 0, atunci următorul bit este de asemenea răsturnat. Acest lucru continuă până când în cele din urmă un pic este răsturnat de la 0 la 1, moment în care oprirea se oprește. Dacă contorul se termină inițial în k 1 biți, răsucim un total de k + 1 biți, luând timpul real k +1 și reducând potențialul cu k −1, deci timpul amortizat este 2. Prin urmare, timpul efectiv de rulare m Operațiile Inc sunt O ( m ).

Aplicații

Metoda funcției potențiale este utilizată în mod obișnuit pentru a analiza grămezile Fibonacci , o formă de coadă prioritară în care eliminarea unui articol necesită timp amortizat logaritmic, iar toate celelalte operații necesită timp amortizat constant. Poate fi, de asemenea, utilizat pentru a analiza arborii splay , o formă de auto-reglare a arborelui binar de căutare cu timp logaritmic amortizat pe operație.

Referințe