Amortizovana analiza
Amortizovana analiza u računarskom smislu predstavlja metod analize algoritama koji razmatra celukupan rad programa. Ideja ove metode govori o tome da, dok određene operacije mogu biti izuzetno skupe, one ne mogu često da se pojavljuju kako bi odgovarale za ceo program, jer će broj jeftinijih operacija nadmašiti skuplje, dugoročno gledano, vraćajući program preko broja iteracija. To je posebno korisno jer se garantuje najgori učinak pre neke pretpostavke o stanju programa.[1][2]
Istorija[uredi | uredi izvor]
Amortizovana analiza je nastala od metode koja se zove agregatna analiza koja je sada u sklopu amortizovane analize. Ova tehnika je prvi put zvanično predstavljena od strane Roberta Trajana u njegovom radu Amortized Computational Complexity(otpisane račurarske konplesnosti), koji ističe potrebu za boljom upotrebom analize od uobičajne.[2]
Amortizacija je prvobitno korišćena za specifičnu vrstu algoritama, posebno one koje uključuju binarna stabla i operacije sa sumama. Sve u svemu, sada je u upotrebi i dolazi do izražaja kada se analiziraju i mnogi drugi algoritmi.
Metod[uredi | uredi izvor]
Metod zahteva poznavanje onih operacija koje su moguće. To je najčešće slučaj sa strukturama podataka koje imaju takvu strukturu, koja ostaje nepromenjena između operacija. Osnovna ideja je da najgora operacija može da menja stanje na takav način da se taj najgori slučaj duže vreme ne može ponovo pojaviti, i na taj način amortizovati svoj trošak, odnosno svoju cenu.
Generalno postoje tri metode za obavljanje amortizovane analize:
- agregatni metod (the aggregate method)
- metod obračuna i (the accounting method)
- metod potencijala (the potential method)
Sve ove metode daju iste odgovore, a koja će se koristiti prvenstveno zavisi od okolnosti i individualnih preferencija.
- Agregatna analiza utvrđuje gornju granicu T(n) ukupne cene niza operacija, a onda računa amortizovani trošak T(n)/n.
- Metod obračuna određuje pojedinačan trošak svake operacije, kombinujući vreme hitno izvršenih operacija sa vremenom budućih izvršenih operacija. Obično, mnoge kratkotrajne operacije akumuliraju "dug" nepovoljnog stanja u malim koracima, dok retke dugotrajne operacije drastično smanjuju "dug“.
- Metod potencijala je sličan metodi obračuna, samo što nagomilava operacije, kako bi kompezovao nedostatak istih.
Upotreba[uredi | uredi izvor]
- Ova analiza je pokazala dobre rezultate u opštoj upotrebi
Reference[uredi | uredi izvor]
- ^ „Lecture 7: Amortized Analysis” (PDF). www.cs.cmu.edu. Pristupljeno 14. 3. 2015.
- ^ a b Fiebrink, Rebecca (2007), Amortized Analysis Explained (PDF), Arhivirano iz originala (PDF) 20. 10. 2013. g., Pristupljeno 03. 05. 2011
Spoljašnje veze[uredi | uredi izvor]
- Obračun i analize konkurencije Arhivirano na sajtu Wayback Machine (5. oktobar 2006)
- Amortizovana Analiza Objašnjenje