Analiza amortizarii este o metoda de analiza a complexitatii de calcul a unui algoritm, utilizata in cazurile in care timpul de executie a unui pas al algoritmului, inmultit cu numarul de pasi, da o estimare prea mare a timpului de executie al intregului algoritm comparativ cu ce este cu adevărat [1] .
Termenul a fost introdus de Robert Tarjan în 1985 [2] . Inițial, analiza amortizată a fost folosită doar pentru o gamă limitată de algoritmi care lucrează cu arbori binari sau operații de unire , dar până acum metoda a devenit omniprezentă și este folosită în analiza multor alte tipuri de algoritmi [3] .
Ideea principală a analizei de amortizare este că orice operațiune cu forță de muncă intensivă modifică starea programului în așa fel încât înainte de următoarea operațiune cu forță de muncă intensivă, vor trece neapărat destul de mici, „amortizând” astfel contribuția a operațiunii cu forță de muncă intensivă. Există trei metode principale pentru efectuarea analizei amortizate: analiza de agregare, metoda plății anticipate și metoda potențialului. Toate trei dau răspunsul corect și într-un caz anume se alege de obicei cel mai convenabil [4] :
Într -o matrice dinamică , pe lângă indexare, există o operație push care adaugă un element la sfârșitul matricei și îi mărește dimensiunea cu unul. Containerele ArrayListîn Java și C++std::vector sunt exemple de astfel de matrice . Dacă dimensiunea matricei este inițial de 4, pot fi adăugate 4 elemente și fiecare adăugare va dura constant. Adăugarea celui de-al cincilea element va necesita crearea unei noi matrice de dimensiunea 8, în care vor fi transferate elementele celui vechi, iar apoi va fi adăugat noul element. Următoarele trei operații de push vor dura din nou timp constant, după care matricea va trebui din nou dublată.
În general, dacă operațiunile push au fost efectuate la o matrice de dimensiune , toate aceste operații vor fi efectuate în timp constant, cu excepția ultimei, care va dura . Din aceasta putem concluziona că costul amortizat al adăugării unui element la o matrice dinamică este [4] .