Amortized ਵਿਸ਼ਲੇਸ਼ਣ ਇੱਕ ਕ੍ਰਮ ਦੇ ਦੌਰਾਨ ਪ੍ਰਤੀ ਓਪਰੇਸ਼ਨ ਔਸਤ ਲਾਗਤ ਨੂੰ ਮਾਪਦਾ ਹੈ, ਭਾਵੇਂ ਵਿਅਕਤੀਗਤ ਓਪਰੇਸ਼ਨ ਕਦੇ-ਕਦਾ ਬਹੁਤ ਵੱਧ ਖਰਚਿਆ ਹੋ। ਇਹ ਵਿਆਖਿਆ ਕਰਦਾ ਹੈ ਕਿ dynamic array ਦਾ append "O(1) amortized" ਕਿਉਂ ਹੈ ਭਾਵੇਂ ਕਦੇ-ਕਦਾ O(n) resizes ਹਾਂ।
ਜਦੋਂ ਇੱਕ dynamic array ਭਰ ਜਾਂਦਾ ਹੈ, ਇਹ ਇੱਕ ਨਵਾਂ array allocate ਕਰਦਾ ਹੈ (ਆਮ ਤੌਰ ਉੱਤੇ ) ਅਤੇ ਸਾਰੇ elements ਦੀ ਕਾਪੀ ਕਰਦਾ ਹੈ — ਇੱਕ O(n) ਕਦਮ। ਪਰ ਕਿਉਂਕਿ capacity ਹੋਵੇ ਜਾਂਦੀ ਹੈ, ਮਹਿੰਗੀਆਂ ਕਾਪੀਆਂ ਤੇਜ਼ੀ ਨਾਲ ਬਹੁਤ ਘੱਟ ਬਾਰ ਹੁੰਦੀਆਂ ਹਨ।
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) |
ਸਥਿਰ ਮਾਤਰਾ ਨਾਲ ਵਧਣ ਨਾਲ ਹਰ insert ਇੱਕ copy trigger ਕਰੇਗਾ, O(n) amortized ਦੇਵੇਗਾ। Multiplicative ਵਾਧਾ ਹੀ ਸੋ ਕਰ ਲਾਗਤ ਫੈਲਾ ਦਿੰਦਾ ਹੈ।
Amortized ਵਿਸ਼ਲੇਸ਼ਣ ਪ੍ਰਦਰਸ਼ਨ ਦੀ ਇੱਕ ਨਿਰਪੱਖ, ਵਾਸਤਵਿਕ ਤਸਵੀਰ ਦਿੰਦਾ ਹੈ — ਇਸ ਤੋਂ ਬਿਨਾਂ, ਤੁਸੀਂ ਗਲਤ ਤਰੀਕੇ ਨਾਲ ਡਰੋਗੇ ਕਿ ਹਰ append ਜਾਂ hash-table insert O(n) ਹੈ।
ਇਹ ਇੱਕ ਮੁੱਖ design ਨਿਯਮ ਨੂੰ ਵੀ ਜਾਇਜ਼ ਠਹਿਰਾਉਂਦਾ ਹੈ: capacity multiplicatively ਵਧਾਓ, ਜੋ dynamic arrays, hash tables, ਅਤੇ string builders ਸਮੁੱਚੇ ਵਿੱਚ ਬਣਿਆ ਹੋਇਆ ਹੈ।
ਵਿਸਤ੍ਰਿਤ ਜਵਾਬਾਂ ਨਾਲ IT ਇੰਟਰਵਿਊ ਸਵਾਲਾਂ ਦੀ ਇੱਕ ਲਾਇਬ੍ਰੇਰੀ — ਜੂਨੀਅਰ ਤੋਂ ਸੀਨੀਅਰ ਤੱਕ।
ਦਾਨ ਕਰੋ