Amortized analysis tkejjel il-cost medju għal operazzjoni fuq sekwenza, ankeż l-operazzjonijiet individwali kultant jisktaw ħafna ħamra. Jispjega għaliex l-append ta' dynamic array huwa "O(1) amortized" minkejja l-resizes O(n) okkażjonali.
Meta dynamic array jimtela, jalloka array ġdid (normalment ) u jikkopja l-elementi kollha — pass O(n). Iżda għax il-capacity , il-kopji għaljin isiru esponenzjalment aktar rari.
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
| Operazzjoni | Worst singlu | Amortized |
|---|---|---|
| append (doubling) | O(n) | O(1) |
Twil b'ammont kostanti ikun għat-trigger ta' kopja għal kull insert, jagħti O(n) amortized. Il-growth multiplikattiv huwa dak li jxerred il-cost barra.
Amortized analysis tagħti stampa ġusta u realistika tal-performance — mingħajr dan, kont taħseb ħażin li kull append jew hash-table insert huwa O(n).
Justifikha wkoll ir-regola ta' disinn kruċjali: itla' l-capacity multiplikattivament, li taħta dynamic arrays, hash tables, u string builders kullimkien.
Librerija ta' mistoqsijiet ta' intervisti tal-IT b'tweġibiet dettaljati — minn Junior sa Senior.
Iddona