Amortized విశ్లేషణ ఒక శ్రేణిలో ఆపరేషన్కు సగటు ఖర్చను కొలుస్తుంది, విడ్డీగా ఆపరేషన్లు కొన్ని సార్లు చాలా ఎక్కువ ఖర్చవుతున్నప్పటికీ. డైనమిక్ array యొక్క append ఎందుకు "O(1) amortized" అని ఇది వివరిస్తుంది, అక్కసॉ O(n) పరిమాణ మార్పులు ఉన్నప్పటికీ.
డైనమిక్ array నిండినప్పుడు, ఇది కొత్త array (సాధారణంగా ) కేటాయిస్తుంది మరియు అన్ని ఎలిమెంట్లను కాపీ చేస్తుంది — 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
| ఆపరేషన్ | చెత్త ఒకటి | Amortized |
|---|---|---|
| append (రెట్టింపు) | O(n) | O(1) |
స్థిరమైన మొత్తంతో పెరిగితే, ప్రతి insert కాపీను ట్రిగర్ చేస్తుంది, O(n) amortized ఇస్తుంది. గుణకార వృద్ధి ఖర్చను కాలిబ్రేట్ చేస్తుంది.
Amortized విశ్లేషణ న్యాయమైన, వాస్తవిక పనితీరు చిత్రాన్ని ఇస్తుంది — దానిలేకుండా, ప్రతి append లేదా hash-table insert O(n) అని తప్పుగా భయపడతారు.
ఇది కూడా ఒక ముఖ్య డిజైన్ నియమాన్ని సమర్థిస్తుంది: సామర్థ్య గుణకార వృద్ధి, ఇది డైనమిక్ arrays, hash tables, మరియు string builders ఎక్కడైనా ఆధారం.