अमोर्टाइजड विश्लेषण एक अनुक्रमको साथमा प्रति अपरेशन औसत लागत मापन गर्दछ, भले पनि अलग-अलग अपरेशनहरु कहिलेकाहीँ धेरै बढी खर्च गर्दछन्। यसले व्याख्या गर्दछ कि गतिशील arrayको append कसरी "O(1) amortized" हो भले अनुसारका O(n) resizes हुन्छन्।
जब एक गतिशील array भर जान्छ, यो एक नयाँ array allocate गर्दछ (सामान्यतः ) र सबै elements कपी गर्दछ — एक 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
| अपरेशन | सबैभन्दा खराब एकल | अमोर्टाइजड |
|---|---|---|
| append (doubling) | O(n) | O(1) |
constant amount को साथ बढ्दै गएमा प्रत्येक insert लाई कपी ट्रिगर गर्नेछ, O(n) amortized दिन्छ। गुणात्मक वृद्धि नै लागत फैलाउने हो।
अमोर्टाइजड विश्लेषणले performance को एक न्याय्य, यथार्थवादी चित्र दिन्छ — यो बिना, तपाईँ गलत तरीकले आशंका गर्नुहुन्छ कि हरेक append वा hash-table insert O(n) हो।
यसले एक मुख्य डिजाइन नियमलाई पनि न्यायसङ्गत ठहराउँदछ: capacity multiplicatively बढाउनुहोस्, जो गतिशील arrays, hash tables, र string builders को पूर्ण कार्यमा अन्तरनिहित छ।