Amortized analysis एक अनुक्रम पर प्रति ऑपरेशन की औसत लागत को मापता है, भले ही कुछ व्यक्तिगत ऑपरेशन कभी-कभी बहुत अधिक खर्च करते हों। यह समझाता है कि dynamic array का append "O(1) amortized" क्यों है, भले ही कभी-कभी O(n) resizes हों।
जब dynamic array भर जाता है, तो यह एक नया array allocate करता है (आमतौर पर ) और सभी तत्वों की नकल करता है — एक O(n) कदम। लेकिन क्योंकि क्षमता होती है, महंगी नकलें 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
| ऑपरेशन | सबसे खराब एक | Amortized |
|---|---|---|
| append (doubling) | O(n) | O(1) |
constant मात्रा से बढ़ना प्रत्येक insert पर copy को trigger करेगा, O(n) amortized देगा। Multiplicative growth ही वह है जो लागत को फैलाता है।
Amortized analysis प्रदर्शन का एक fair, realistic चित्र देता है — इसके बिना, आप गलत तरीके से डरते कि हर append या hash-table insert O(n) है।
यह एक key design rule को भी justify करता है: क्षमता को multiplicatively बढ़ाएं, जो dynamic arrays, hash tables, और string builders को हर जगह उपयोग करता है।