Avskrivningsanalys

Amorteringsanalys är en metod för att analysera beräkningskomplexiteten hos en algoritm, som används i de fall då exekveringstiden för ett steg i algoritmen, multiplicerat med antalet steg, ger en för stor uppskattning av exekveringstiden för hela algoritmen jämfört med vad det egentligen är [1] .

Historik

Termen introducerades av Robert Tarjan 1985 [2] . Till en början användes amorterad analys endast för ett begränsat antal algoritmer som arbetar med binära träd eller fackliga operationer , men vid det här laget har metoden blivit allestädes närvarande och används i analysen av många andra typer av algoritmer [3] .

Metod

Huvudtanken med amorteringsanalys är att varje arbetsintensiv operation förändrar programmets tillstånd på ett sådant sätt att innan nästa arbetsintensiva operation kommer en hel del små nödvändigtvis att passera, och därigenom "amortera" bidraget av den arbetsintensiva verksamheten. Det finns tre huvudsakliga metoder för att genomföra amorterad analys: aggregeringsanalys, förskottsbetalningsmetod och potentiell metod. Alla tre ger det korrekta svaret och i ett särskilt fall väljs vanligtvis det lämpligaste [4] :

Vid aggregeringsanalys beräknas en övre uppskattning för verksamhetens utförandetid, sedan likställs amorteringskomplexiteten för en operation med [4] . $T(n)$ $n$ ${\textstyle T(n)/n}$
I förskottsbetalningsmetoden varje transaktion i förväg ett upplupet anskaffningsvärde , som kan skilja sig från dess faktiska anskaffningsvärde. Samtidigt har "billigare" transaktioner vanligtvis upplupet anskaffningsvärde som är högre än den verkliga, och mer "dyrare" har upplupet kostnad lägre än den verkliga. På grund av detta, när man utför billiga transaktioner, ackumuleras en del belopp som kan "förbrukas" på att utföra en transaktion vars upplupet kostnad är lägre än den verkliga. Det antas att det initiala beloppet är lika med noll, och om det inte blir negativt under algoritmen, kommer den totala körtiden för algoritmen att vara lika med skillnaden mellan den totala amorterade kostnaden för operationer och det ackumulerade beloppet. Den upplupna kostnaden för transaktioner är således en övre uppskattning av den verkliga kostnaden, förutsatt att det ackumulerade beloppet inte blir negativt [4] .
I metoden för potentialer beräknas den ackumulerade summan som en funktion ("potential") av tillståndet för datastrukturen. Den upplupna kostnaden i detta fall är lika med summan av den verkliga kostnaden och potentialförändringen [4] .

Exempel

Dynamisk array

I en dynamisk array finns det förutom indexering en push- operation som lägger till ett element i slutet av arrayen och ökar dess storlek med ett. Behållare ArrayListi Java och C++std::vector är exempel på en sådan array . Om arraystorleken är 4 initialt, kan 4 element läggas till den, och varje tillägg kommer att ta konstant tid. Att lägga till det femte elementet kommer att kräva skapandet av en ny array av storlek 8, till vilken elementen i det gamla kommer att överföras, och sedan kommer det nya elementet att läggas till. De kommande tre push- operationerna kommer återigen att ta konstant tid, varefter matrisen återigen måste fördubblas.

I allmänhet, om push - operationer utfördes till en array av storlek , kommer alla dessa operationer att utföras i konstant tid, förutom den sista, som tar . Av detta kan vi dra slutsatsen att den amortiserade kostnaden för att lägga till ett element till en dynamisk array är [4] . $n+1$ $n$ $\Theta(n)$ ${\textstyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}$

Anteckningar

Allan Borodinoch Ran El-Yaniv. Onlineberäkning och konkurrensanalys (engelska) . - Cambridge University Press , 1998. - S. 20,141.

↑ Föreläsning 7: Amortiserad analys . Carnegie Mellon University . Hämtad 14 mars 2015. Arkiverad från originalet 26 februari 2015. (obestämd)
↑ Tarjan, Robert Endre . Amortiserad beräkningskomplexitet // SIAM Journal om algebraiska och diskreta metoder : journal. - 1985. - April ( vol. 6 , nr 2 ). - s. 306-318 . - doi : 10.1137/0606031 .
↑ Rebecca Fiebrink (2007), Amortized Analysis Explained , < http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf > . Hämtad 3 maj 2011. Arkiverad 20 oktober 2013 på Wayback Machine
↑ 1 2 3 4 5 Kozen, Dexter CS 3110 Föreläsning 20: Amortiserad analys . Cornell University (våren 2011). Hämtad 14 mars 2015. Arkiverad från originalet 3 oktober 2018. (obestämd)