Analýza odpisů

Amortizační analýza je metoda analýzy výpočetní složitosti algoritmu, která se používá v případech, kdy doba provádění jednoho kroku algoritmu vynásobená počtem kroků poskytuje příliš velký odhad doby provádění celého algoritmu ve srovnání s co to vlastně je [1] .

Historie

Termín zavedl Robert Tarjan v roce 1985 [2] . Zpočátku byla amortizovaná analýza používána pouze pro omezený rozsah algoritmů pracujících s binárními stromy nebo sjednocovacími operacemi , ale nyní se tato metoda stala všudypřítomnou a používá se při analýze mnoha dalších typů algoritmů [3] .

Metoda

Hlavní myšlenkou analýzy amortizace je, že jakákoli pracně náročná operace změní stav programu tak, že před další pracovně náročnou operací nutně projde poměrně hodně malých, čímž se příspěvek „amortizuje“. pracovně náročného provozu. Existují tři hlavní metody provádění analýzy amortizace: agregační analýza, metoda platby předem a metoda potenciální. Všechny tři dávají správnou odpověď a v konkrétním případě je obvykle vybrána ta nejvhodnější [4] :

Při agregační analýze se vypočítá horní odhad doby provádění operací, poté se složitost amortizace jedné operace vyrovná [4] . $T(n)$ $n$ ${\textstyle T(n)/n}$
U způsobu platby předem každé transakci předem přiřazena zůstatková hodnota , která se může lišit od její skutečné ceny. Zároveň „levnější“ transakce mají obvykle zůstatkovou cenu vyšší než reálná a „dražší“ mají zůstatkovou cenu nižší než skutečná. Díky tomu se při provádění levných transakcí hromadí určitá částka, kterou lze „utratit“ za provedení transakce, jejíž amortizovaná hodnota je nižší než skutečná. Předpokládá se, že počáteční částka je rovna nule, a pokud se během algoritmu nestane zápornou, pak se celková doba běhu algoritmu bude rovnat rozdílu mezi celkovými amortizovanými náklady operací a kumulovanou částkou. Zůstatková hodnota transakcí je tedy horním odhadem skutečných nákladů za předpokladu, že kumulovaná částka nebude záporná [4] .
V metodě potenciálů se akumulovaný součet vypočítá jako funkce („potenciál“) stavu datové struktury. Naběhlá hodnota se v tomto případě rovná součtu skutečných nákladů a změny potenciálu [4] .

Příklady

Dynamické pole

V dynamickém poli kromě indexování existuje operace push , která přidá prvek na konec pole a zvětší jeho velikost o jednu. Příkladem takového pole jsou kontejnery ArrayListv Javě a C++ . Pokud je velikost pole zpočátku 4, lze do něj přidat 4 prvky a každé přidání bude trvat konstantní čas. Přidání pátého prvku bude vyžadovat vytvoření nového pole o velikosti 8, do kterého se přenesou prvky starého a následně se přidá prvek nový. Další tři operace push budou opět trvat konstantní čas, po kterém bude nutné pole opět zdvojnásobit. std::vector

Obecně platí, že pokud byly operace push provedeny na poli velikosti , budou všechny tyto operace provedeny v konstantním čase, kromě poslední, která bude trvat . Z toho můžeme usoudit, že amortizované náklady na přidání prvku do dynamického pole jsou [4] . $n+1$ $n$ $\Opalování)$ ${\textstyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}$

Poznámky

Allan Borodina Ran El-Yaniv. Online výpočty a konkurenční analýza (anglicky) . - Cambridge University Press , 1998. - S. 20,141.

↑ Přednáška 7: Amortizovaná analýza . Univerzita Carnegie Mellon . Získáno 14. března 2015. Archivováno z originálu 26. února 2015. (neurčitý)
↑ Tarjan, Robert Endre . Amortizovaná výpočetní složitost // SIAM Journal o algebraických a diskrétních metodách : deník. - 1985. - Duben ( roč. 6 , č. 2 ). - str. 306-318 . - doi : 10.1137/0606031 .
↑ Rebecca Fiebrink (2007), Amortized Analysis Explained , < http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf > . Získáno 3. května 2011. Archivováno 20. října 2013 na Wayback Machine
↑ 1 2 3 4 5 Kožen, Dexter CS 3110 Přednáška 20: Amortizovaná analýza . Cornell University (jaro 2011). Získáno 14. března 2015. Archivováno z originálu 3. října 2018. (neurčitý)