અમોર્ટાઇઝ્ડ એનાલીસીસ એક ક્રમ પર પ્રતિ ઑપરેશન સરેરાશ કિંમત માપે છે, જોકે કેટલીક વ્યક્તિગત કામગીરી ક્યારેક વધુ કિંમત ધરાવે છે. તે સમજાવે છે કે શા માટે ડાયનામીક એરેનું append "O(1) અમોર્ટાઇઝ્ડ" છે, ભલે ક્યારેક O(n) રીસાઇઝીંગ થાય.
જ્યારે ડાયનામીક એરે ભરી જાય છે, ત્યારે તે નવું એરે (સામાન્ય રીતે ) ફાળવે છે અને બધા તત્વોની નકલ કરે છે — એક O(n) પગલું. પરંતુ કારણ કે ક્ષમતા થાય છે, મોંઘી નકલ ઘાતાંકીય રીતે દુર્લભ બની જાય છે.
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 (બમણું) | O(n) | O(1) |
સ્થિર માત્રા વડે વૃદ્ધિ પામવું દરેક ઇનસર્ટ પર નકલ વધારશે, O(n) અમોર્ટાઇઝ્ડ આપશે. ગુણાકાર વૃદ્ધિ તે છે જે કિંમત ફેલાવે છે.
અમોર્ટાઇઝ્ડ એનાલીસીસ કામગીરીનું વાજબી, વાસ્તવિક ચિત્ર આપે છે — તેના વિના, તમે ખોટાં રીતે ડરી જાશો કે દરેક append અથવા hash-table ઇનસર્ટ O(n) છે.
તે એક મુખ્ય ડિઝાઇન નિયમને પણ સમર્થન આપે છે: ક્ષમતા ગુણાકારીય રીતે વૃદ્ધિ કરો, જે ડાયનામીક એરે, hash table અને string builder સર્વત્ર આધારિત છે.