Analiza amortizată măsoară costul mediu per operație peste o secvență, chiar și atunci când operațiile individuale ocazional costă mult mai mult. Explică de ce append unei matrice dinamice este "O(1) amortizat" în ciuda redimensionării ocazionale O(n).
Când o matrice dinamică se umple, alocă o nouă matrice (de obicei ) și copiază toate elementele — o etapă O(n). Dar deoarece capacitatea se , copiile scumpe devin exponențial mai rare.
Appending into a doubling array (cap shown):
ops: 1 2 3 4 5 6 7 8 9
cap: 1 2 4 4 8 8 8 8 16
copy: * * * * * <- copies at 1,2,4,8,16...
To insert n elements, total copy work =
1 + 2 + 4 + ... + n ≈ 2n (geometric series)
Total cost for n inserts = O(n)
Amortized cost per insert = O(n)/n = O(1)
arr = []
for i in range(1_000_000):
arr.append(i) # almost always O(1); rarely O(n) during a resize
| Operație | Cel mai rău caz unic | Amortizat |
|---|---|---|
| append (dublare) | O(n) | O(1) |
Crescând cu o cantitate constantă ar determina fiecare inserare să declanșeze o copie, dând O(n) amortizat. Creșterea multiplicativă este ceea ce distribuie costul.
Analiza amortizată oferă o imagine corectă și realistă a performanței — fără ea, ai teme pe bună dreptate că fiecare append sau inserare în tabel hash este O(n).
Justifică, de asemenea, o regulă de design cheie: creștere exponențială a capacității, care stă la baza matricelor dinamice, tabelelor hash și constructorilor de string peste tot.
O bibliotecă de întrebări de interviu IT cu răspunsuri detaliate — de la Junior la Senior.
Donează