Begrijpen en berekenen van de geamortiseerde kosten van dynamische array-operaties

Dynamische arrays zijn datastructuren die automatisch verkleinen wanneer ze capaciteit bereiken. Het begrijpen van hun geamortiseerde kosten helpt hun efficiëntie te evalueren over meerdere operaties.

Wat is Amortized Cost?

De afschrijvingskosten zijn de gemiddelde kosten per operatie over een reeks operaties. Het verzacht de hoge kosten van incidentele herindeling door ze over vele goedkope operaties te verdelen.

Dynamische arraybewerkingen

Gemeenschappelijke operaties op dynamische arrays omvatten invoegen, verwijderen en wijzigen. Invoegen aan het einde is meestal de meest voorkomende operatie, die kan leiden tot het wijzigen van de grootte wanneer de capaciteit wordt overschreden.

Berekening van de afgeschreven kosten

Bij het invoegen van elementen verdubbelt de array in grootte wanneer deze vol is. De kosten van het herschalen zijn inclusief het kopiëren van alle bestaande elementen naar de nieuwe array. Hoewel grootte wijzigen duur is, komt het zelden voor.

Als bijvoorbeeld een array begint met capaciteit 1, kan de volgorde van de kosten van het wijzigen van de grootte over meerdere invoegsels worden samengevat als:

• Invoegen 1 element: kosten 1
• Tweede element invoegen: formaat wijzigen (kosten 1), totale kosten 2
• 3e element invoegen: formaat wijzigen (kosten 2) Totale kosten 3
• 4e element invoegen: formaat wijzigen (kosten 4), totale kosten 4

De totale kosten boven n invoegsels zijn evenredig aan 2n, waardoor de afgeschreven kosten per inbrenging ongeveer O(1).