Dynamiska arrayer är datastrukturer som automatiskt ändrar storlek när de når kapacitet. Förstå deras amorterade kostnad hjälper till att utvärdera deras effektivitet över flera operationer.

Vad är Amortized Cost?

Den amorterade kostnaden är den genomsnittliga kostnaden per drift över en verksamhetssekvens. Det jämnar ut de höga kostnaderna för tillfällig storlek genom att distribuera dem över många billiga operationer.

Dynamisk Array Operations

Vanliga operationer på dynamiska arrays inkluderar införande, radering och storlek. Införande i slutet är vanligtvis den vanligaste operationen, vilket kan utlösa storleksstorlek när kapaciteten överskrids.

Beräkning av den amorterade kostnaden

När man sätter in element, dubblar arrayen i storlek när den är full. Kostnaden för storleksstorlek innebär att kopiera alla befintliga element till den nya arrayen. Även om storleken är kostsam, sker den sällan.

Om en array börjar med kapacitet 1, kan sekvensen av storleksstorlek över flera insättningar sammanfattas som:

  • Infoga 1 element: kostnad 1
  • Infoga 2: a elementet: resize (kostnad 1), total kostnad 2
  • Infoga 3: e elementet: resize (kostnad 2), total kostnad 3
  • Infoga 4: e elementet: resize (kostnad 4), total kostnad 4

Den totala kostnaden över n-insättningar är proportionell mot 2n, vilket gör den amorterade kostnaden per införande cirka O(1).