Dynamiske arrays er datastrukturer som automatisk endrer størrelsen når de når kapasitet. Å forstå deres amortiserte kostnader bidrar til å evaluere effektiviteten sin over flere operasjoner.

Hva er amortisert kostnad?

Den amortiserte kostnaden er gjennomsnittlige kostnader per operasjon over en sekvens av operasjoner. Det jevner ut de høye kostnadene ved å endre størrelsen av tidvis ved å distribuere dem over mange billige operasjoner.

Dynamiske array-operasjoner

Vanlige operasjoner på dynamiske tabeller inkluderer innsetting, sletting og endring. Innsetting i slutten er vanligvis den hyppigste operasjonen, som kan utløse endring når kapasiteten er overskredet.

Beregne den amortiserte kostnaden

Når du setter inn elementer, dobler array i størrelse når full. Kostnaden for endring av størrelse innebærer å kopiere alle eksisterende elementer til den nye array. Selv om endring er kostbart, oppstår det sjelden.

For eksempel kan sekvensen av størrelsene over flere innsettinger oppsummeres som dersom en tabell starter med kapasitet 1, idet sekvensen av omstørrelseskostnader kan oppsummeres som:

  • Sett inn 1 element: kostnad 1
  • Sett inn 2. element: størrelse (kostnad 1), total kostnad 2
  • Sett inn 3. element: størrelse (kostnad 2), total kostnad 3
  • Sett inn 4. element: størrelse (koste 4), total kostnad 4

Den totale kostnaden over n-innsettinger er proporsjonal med 2n, noe som gjør den amortiserte kostnaden per innsetting ca. O(1).