Array-urile dinamice sunt structuri de date care redimensionează automat când ating capacitatea. Înțelegerea costurilor amortizate ajută la evaluarea eficienței lor asupra operațiunilor multiple.

Ce este costul amortizat?

Costul amortizat este costul mediu pe operațiune pe o serie de operațiuni. Acesta reduce costurile ridicate ale redimensionării ocazionale prin distribuirea lor în multe operațiuni ieftine.

Operațiuni dinamice de array

Operaţiunile comune pe array-uri dinamice includ inserţie, ştergere, şi redimensionare. Inserarea la sfârşit este de obicei cea mai frecventă operaţiune, care poate declanşa redimensionarea atunci când capacitatea este depăşită.

Calcularea costului amortizat

Atunci când introduceți elemente, matricea se dublează în mărime atunci când este completă. Costul redimensionării implică copierea tuturor elementelor existente la noul array. Deși redimensionarea este costisitoare, aceasta are loc rar.

De exemplu, dacă un array începe cu capacitatea 1, secvența de redimensionare a costurilor pe mai multe inserții poate fi rezumată ca:

  • Se introduce 1 element: cost 1
  • Se introduce al doilea element: redimensionare (cost 1), costul total 2
  • Se introduce al treilea element: redimensionare (cost 2), costul total 3
  • Se introduce al patrulea element: redimensionare (cost 4), costul total 4

Costul total peste n inserții este proporțional cu 2n, ceea ce face costul amortizat per inserție aproximativ O(1).