Amortized analysis ایک sequence پر operations کی average cost کو ماپتا ہے، یہاں تک کہ جب انفرادی operations بعض اوقات بہت زیادہ مہنگے ہوں۔ یہ بتاتا ہے کہ dynamic array کا append "O(1) amortized" کیوں ہے اگرچہ بعض اوقات O(n) resizes ہوتے ہیں۔
جب dynamic array بھر جاتا ہے، تو یہ ایک نیا array allocate کرتا ہے (عام طور پر ) اور تمام elements کو copy کرتا ہے — یہ ایک O(n) step ہے۔ لیکن کیونکہ capacity ہوتی ہے، مہنگے copies exponentially کم بار ہوتے ہیں۔
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 | Worst single | Amortized |
|---|---|---|
| append (doubling) | O(n) | O(1) |
اگر capacity کو constant amount سے بڑھایا جائے تو ہر insert ایک copy کو trigger کرے گا، جو O(n) amortized دے گا۔ Multiplicative growth وہی ہے جو cost کو پھیلاتا ہے۔
Amortized analysis ایک منصفانہ اور حقیقی performance کی تصویر دیتا ہے — اس کے بغیر، آپ غلط طریقے سے یہ سوچیں گے کہ ہر append یا hash-table insert O(n) ہے۔
یہ ایک اہم design rule کو بھی justify کرتا ہے: capacity کو multiplicatively بڑھائیں، جو dynamic arrays، hash tables، اور string builders میں ہر جگہ underlying ہے۔