Potentiaalien menetelmä (poistoanalyysi)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7. huhtikuuta 2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Potentiaalinen menetelmä on yksi poistoanalyysimenetelmistä, jonka avulla voit "tasoittaa" kalliiden mutta harvinaisten operaatioiden vaikutusta algoritmin laskennalliseen kokonaismonimutkaisuuteen [1] [2] .

Määritelmät

Potentiaalien menetelmässä otetaan käyttöön funktio , joka linkittää tietorakenteen tilan johonkin ei-negatiiviseen numeroon. Tämän funktion merkitys on, että jos on rakenteen nykyinen tila, niin on arvo, joka kuvaa "kalliin" operaatioiden työmäärää, joka on jo "maksettu" halvemmalla operaatiolla, mutta jota ei ole tuotettu. Siten sitä voidaan pitää tiettyyn tilaan liittyvän potentiaalienergian analogina [1] [2] . Aluksi potentiaalifunktion arvoksi asetetaan yleensä nolla. $\Phi$ $S$ $\Phi (S)$ $\Phi (S)$

Olkoon jokin sarjasta erillinen operaatio, olkoon rakenteen tila ennen tätä operaatiota ja sen jälkeen. Silloin toiminnan jaksotettu monimutkaisuus on $o$ $S_{ennen}$ $S_{after}$ $o$

T_{\mathrm {amortized} }(o)=T_{\mathrm {todellinen} }(o)+\Phi (S_{\mathrm {jälkeen} })-\Phi (S_{\mathrm {ennen} }).

Poistojen ja todellisen arvon välinen suhde

Toimintosarjan jaksotettu kokonaishinta on kelvollinen yläraja kyseisen toimintosarjan todelliselle kustannukselle.

Toimintosarjalle voidaan määrittää: ${\displaystyle O=o_{1},o_{2},\dots ,o_{n))$

Poistoaika yhteensä: $T_{\mathrm {amortized} }(O)=\sum _{i=0}^{n}T_{\mathrm {amortized} }(o_{i}),$
Reaaliaika yhteensä: $T_{\mathrm {todellinen} }(O)=\summa _{i=0}^{n}T_{\mathrm {todellinen} }(o_{i}).$

Näissä merkinnöissä:

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

Siten potentiaalifunktioarvojen sarja muodostaa teleskooppisen summan , jossa peräkkäiset alku- ja loppupotentiaalifunktioarvot kumoavat toisensa.

Siitä, että epätasa- arvo seuraa , kuten aiemmin sanottiin. $\Phi (S_{0})=0$ $\Phi (S_{n})\geq 0$ $T_{\mathrm {todellinen} }(O)\leq T_{\mathrm {amortized} }(O)$

Esimerkkejä

Pino massapoistoilla

Voit harkita pinon muunnelmaa, joka tukee seuraavia toimintoja:

alusta - luo tyhjä pino.
push - lisää yksi elementti pinon yläosaan suurentamalla sen kokoa . $yksi$
pop(k) - poista elementit pinon yläosasta, jos se ei ylitä nykyistä pinon kokoa. $k$ $k$

Yksi operaatio pop(k) vie aikaa, kun taas kokonaisajoaika voidaan analysoida käyttämällä seuraavaa potentiaalifunktiota, joka on yhtä suuri kuin pinon elementtien lukumäärä . Tämä arvo on aina ei-negatiivinen, kun taas push -operaatio toimii vakiolla ja kasvaa yhdellä, ja pop -operaatio toimii arvolla , mutta myös pienentää potentiaalifunktiota , joten sen kuoletusaika on myös vakio. Tästä seuraa, että minkä tahansa toimintosarjan kokonaissuoritusaika on yhtä suuri pahimmassa tapauksessa. $O(k)$ $\Phi (S)$ $S$ $\Phi$ $O(k)$ $k$ $m$ $O(m)$

Binäärilaskuri

Toinen esimerkki on binäärilukuna toteutettu laskuri , joka tukee seuraavia toimintoja:

alusta – luo laskuri arvolla . $0$
lisäys - lisää laskurin arvoa . $yksi$

Osoittaaksesi, että inc :n jaksotettu kustannus on , harkitse potentiaalista funktiota, joka on yhtä suuri kuin laskuribittien lukumäärä (laskurin Hamming - paino ). Tarvittaessa tällainen funktio on aina ei-negatiivinen ja on aluksi yhtä suuri kuin . Inc - toiminto kääntää ensin laskurin vähiten merkitsevän bitin , ja sitten, jos se oli , toistaa samaa seuraavalla bitillä, kunnes se osuu . Jos ennen sitä laskurin bittitietueen lopussa oli yksittäisiä bittejä, bitti on invertoitava , kuluttamalla reaaliaikayksiköitä ja vähentäen potentiaalia . Siten inc -operaation jaksotettu hankintameno on yhtä suuri ja sen seurauksena inc - toimintojen suoritusaika on yhtä suuri kuin . $O(1)$ $yksi$ $0$ $yksi$ $0$ $k$ $k+1$ $k+1$ $k-1$ $2$ $m$ $O(m)$

Sovellukset

Potentiaalien menetelmää käytetään yleisesti Fibonacci-kasojen analysointiin , jossa elementin erottaminen vie amortisoitua logaritmisaikaa ja kaikki muut operaatiot kulutettua vakioaikaa [3] . Sitä voidaan myös käyttää osoittamaan, että splay-puulla on logaritminen jaksotettu toimintameno [4] .

Muistiinpanot

↑ 1 2 Goodrich, Michael T. & Tamassia, Roberto (2002), 1.5.1 Amortization Techniques, Algorithm Design: Foundations, Analysis and Internet-esimerkit , Wiley, s. 36-38 .
↑ 1 2 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 18.3 Potential Method // Algoritmit: Rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - S. 412-416. — ISBN 5-8459-0857-4 .
↑ Cormen et al., luku 20, "Fibonacci Heaps", s. 476-497.
↑ Goodrich ja Tamassia, jakso 3.4, "Splay Trees", s. 185-194.