Értékcsökkenési elemzés

Az amortizációanalízis egy algoritmus számítási bonyolultságának elemzésére szolgáló módszer , amelyet olyan esetekben használnak, amikor az algoritmus egy lépésének végrehajtási ideje a lépések számával szorozva túl nagy becslést ad a teljes algoritmus végrehajtási idejére a mi ez valójában [1] .

Történelem

A kifejezést Robert Tarjan vezette be 1985-ben [2] . Kezdetben az amortizált elemzést a bináris fákkal vagy unióműveletekkel dolgozó algoritmusok korlátozott köréhez használták , de mára a módszer mindenütt elterjedt, és számos más típusú algoritmus elemzésére is használják [3] .

Módszer

Az amortizációelemzés fő gondolata az, hogy minden munkaigényes művelet megváltoztatja a program állapotát úgy, hogy a következő munkaigényes művelet előtt elég sok kicsi átmegy, ezáltal „amortizálja” a hozzájárulást. a munkaigényes művelet. Három fő módszer létezik az amortizált elemzés elvégzésére: aggregációs elemzés, előtörlesztési módszer és potenciális módszer. Mindhárom megadja a helyes választ, és adott esetben általában a legkényelmesebbet választják [4] :

Az aggregáló analízis során a műveletek végrehajtási idejére egy felső becslést számolunk , majd egy művelet amortizációs összetettségét [4] -nek adjuk meg . $T(n)$ $n$ ${\textstyle T(n)/n}$
Az előtörlesztési módban tranzakcióhoz előre hozzárendelnek egy amortizált bekerülési értéket, amely eltérhet a tényleges bekerülési értéktől. Ugyanakkor az „olcsóbb” tranzakciók amortizált bekerülési értéke általában magasabb, mint a valósé, a „drágábbak” amortizált bekerülési értéke alacsonyabb, mint a valósé. Emiatt az olcsó tranzakciók lebonyolítása során felhalmozódik némi összeg, amelyet olyan tranzakció végrehajtására lehet „költeni”, amelynek amortizált bekerülési értéke alacsonyabb, mint a valós. Feltételezzük, hogy a kezdeti összeg nullával egyenlő, és ha nem válik negatívvá az algoritmus során, akkor az algoritmus teljes futási ideje megegyezik a műveletek teljes amortizált költsége és a felhalmozott összeg különbségével. Így a tranzakciók amortizált bekerülési értéke a valós költség felső becslése, feltéve, hogy a felhalmozott összeg nem lesz negatív [4] .
A potenciálok módszerében a halmozott összeget az adatstruktúra állapotának függvényeként ("potenciálként") számítják ki. Az amortizált bekerülési érték ebben az esetben egyenlő a valós költség és a potenciálváltozás összegével [4] .

Példák

Dinamikus tömb

A dinamikus tömbben az indexelésen kívül van egy push művelet , amely hozzáad egy elemet a tömb végéhez, és eggyel növeli a méretét. ArrayListA Java és a C++ konténerei std::vectorpéldák egy ilyen tömbre . Ha a tömb mérete kezdetben 4, akkor 4 elemet lehet hozzáadni hozzá, és minden hozzáadás állandó időt vesz igénybe. Az ötödik elem hozzáadásához létre kell hozni egy új 8-as méretű tömböt, amelybe átkerülnek a régi elemei, majd hozzáadódik az új elem. A következő három push művelet ismét állandó időt vesz igénybe, ezután ismét meg kell duplázni a tömböt.

Általánosságban elmondható, hogy ha a push műveleteket egy méretű tömbre hajtották végre, akkor ezek a műveletek állandó időben kerülnek végrehajtásra, kivéve az utolsót, amely a következőt veszi igénybe . Ebből arra következtethetünk, hogy egy elem dinamikus tömbhöz való hozzáadásának amortizált költsége [4] . $n+1$ $n$ $\Theta(n)$ ${\textstyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}$

Jegyzetek

Allan Borodinés Ran El-Yaniv. Online számítás és versenyelemzés (angol) . - Cambridge University Press , 1998. - P. 20,141.

↑ 7. előadás: Amortizált elemzés . Carnegie Mellon Egyetem . Letöltve: 2015. március 14. Az eredetiből archiválva : 2015. február 26.. (határozatlan)
↑ Tarjan, Robert Endre . Amortizált számítási komplexitás // SIAM Journal on Algebraic and Discrete Methods : folyóirat. - 1985. - április ( 6. köt . 2. sz .). - P. 306-318 . - doi : 10.1137/0606031 .
↑ Rebecca Fiebrink (2007), Amortized Analysis Explained , < http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf > . Letöltve: 2011. május 3. Archiválva : 2013. október 20. a Wayback Machine -nél
↑ 1 2 3 4 5 Kozen, Dexter CS 3110 20. előadás: Amortizált elemzés . Cornell Egyetem (2011 tavasza). Letöltve: 2015. március 14. Az eredetiből archiválva : 2018. október 3. (határozatlan)