Complexitatea temporală amortizată este modul de exprimare a complexității temporale atunci când un algoritm are o complexitate temporală foarte proastă doar o dată la un moment dat, în afară de complexitatea temporală care apare de cele mai multe ori. Un bun exemplu ar fi o ArrayList, care este o structură de date care conține o matrice și care poate fi extinsă. O altă definiție de la Stack Overflow este timpul mediu necesar pentru fiecare operațiune, dacă efectuați mai multe operații.
Când ArrayList atinge capacitatea array-ului din el, atunci creează un nou array cu dimensiunea dublată a vechiului array și copiază toate elementele din vechiul array în noul array. În ArrayList, există două complexități de timp; una este O(1) și cealaltă este O(n).
Când array-ul din el nu și-a atins capacitatea și are încă suficient spațiu pentru a introduce elemente
Pentru a introduce un element în array în acest caz, trebuie doar să punem elementul după ultimul element. Încă mai avem spațiu pentru a insera elemente.
Când array-ul din el și-a atins capacitatea și trebuie să se recreeze cu dimensiunea dublată
Aray-ul și-a atins capacitatea și nu mai avem spații disponibile. Atunci trebuie să creăm o matrice complet nouă cu dimensiunea dublată. Și apoi să copiem elementele din vechea matrice în cea nouă, ceea ce durează O(n) unde n este capacitatea vechii matrice și cel mai rău caz.
Pentru a exprima aceste două complexități de timp, timpul amortizat este aici. Ceea ce face este să ne permită să descriem cel mai rău caz se întâmplă o dată la un moment dat, de fiecare dată când matricea internă își atinge capacitatea.
Dar o dată ce se întâmplă, nu se va mai repeta pentru o perioadă atât de lungă încât costul este „amortizat”. (Cracking the Coding Interview 6th edition 43)
Atunci cum descriem cele două complexități?
În cazul ArrayList, putem spune că
Inserția durează O(n) atunci când capacitatea a fost atinsă, iar timpul amortizat pentru fiecare inserție este O(1).
Dar să fim exacți pentru cea mai rea complexitate de timp fără a simplifica acest timp. Dacă capacitatea internă a matricei începe cu 1, atunci capacitățile vor fi 1, 2, 4, 8, 16… X când atinge capacitatea și se dublează. Este nevoie de 1, 2, 4, 8, 16, … X elemente pentru a fi copiate în noua matrice în funcție de capacitatea care a fost atinsă. Astfel, complexitatea timpului va fi de 1 + 2 + 2 + 4 + 8 + 16 +… X. Dacă vă gândiți de la X, aceasta va fi X + X/2 + X/4 + X/8… + 1 = 2X aproximativ. Deci, cu alte cuvinte, cu exactitate,
Inserția durează O(2X) atunci când a fost atinsă capacitatea lui X, iar timpul amortizat pentru fiecare inserție este O(1).
.
