Amortisert analyse måler gjennomsnittlig kostnad per operasjon over en sekvens, selv om enkelte operasjoner av og til koster mye mer. Det forklarer hvorfor en dynamisk arrays append er "O(1) amortisert" til tross for tilfeldig O(n) endring av størrelse.
Når en dynamisk array blir full, allokerer den en ny array (vanligvis ) og kopierer alle elementer — ett O(n) trinn. Men fordi kapasiteten , blir dyre kopier eksponentielt sjeldnere.
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
| Operasjon | Verste enkelt | Amortisert |
|---|---|---|
| append (fordobling) | O(n) | O(1) |
Å vokse med et konstant beløp ville få hver inserering til å utløse en kopi, noe som gir O(n) amortisert. Multiplikativ vekst er det som fordeler kostnadene.
Amortisert analyse gir et rettferdig, realistisk bilde av ytelse — uten det ville du urettmessig frykte at hver append eller hash-table inserering er O(n).
Det begrunner også en viktig designregel: vokser kapasitet multiplikativt, som ligger til grunn for dynamiske arrays, hash-tabeller og string builders overalt.
Et bibliotek av IT-intervjuspørsmål med detaljerte svar — fra Junior til Senior.
Doner