Amortiseret analyse måler den gennemsnitlige omkostning pr. operation over en sekvens, selv når individuelle operationer lejlighedsvis koster meget mere. Det forklarer, hvorfor en dynamisk arrays append er "O(1) amortized" på trods af lejlighedsvise O(n) ændringer af størrelse.
Når et dynamisk array bliver fuldt, tildeler det et nyt array (normalt ) og kopierer alle elementer — et O(n) trin. Men fordi kapaciteten , bliver dyre kopier eksponentielt sjældnere.
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
| Operation | Værste enkelt | Amortiseret |
|---|---|---|
| append (doubling) | O(n) | O(1) |
At vokse med et konstant beløb ville udløse en kopi ved hver indsættelse, hvilket giver O(n) amortiseret. Multiplikativ vækst er det, der spreder omkostningerne.
Amortiseret analyse giver et retfærdigt, realistisk billede af ydeevnen — uden det ville du forkert frygte, at hver append eller hash-table-indsættelse er O(n).
Det begrunder også en nøgle-designregel: vokse kapaciteten multiplikativt, som ligger bag dynamiske arrays, hash-tabeller og string-bygere overalt.
Et bibliotek af IT-interviewspørgsmål med detaljerede svar — fra Junior til Senior.
Donér