Amortized ਵਿਸ਼ਲੇਸ਼ਣ ਕੀ ਹੈ, dynamic array resizing ਦੀ ਉਦਾਹਰਣ ਦੇ ਨਾਲ?

Question

Accepted Answer

**Amortized ਵਿਸ਼ਲੇਸ਼ਣ** ਇੱਕ ਕ੍ਰਮ ਦੇ ਦੌਰਾਨ **ਪ੍ਰਤੀ ਓਪਰੇਸ਼ਨ ਔਸਤ ਲਾਗਤ** ਨੂੰ ਮਾਪਦਾ ਹੈ, ਭਾਵੇਂ ਵਿਅਕਤੀਗਤ ਓਪਰੇਸ਼ਨ ਕਦੇ-ਕਦਾ ਬਹੁਤ ਵੱਧ ਖਰਚਿਆ ਹੋ। ਇਹ ਵਿਆਖਿਆ ਕਰਦਾ ਹੈ ਕਿ dynamic array ਦਾ `append` "**O(1) amortized**" ਕਿਉਂ ਹੈ ਭਾਵੇਂ ਕਦੇ-ਕਦਾ O(n) resizes ਹਾਂ।

## Dynamic array ਦੀ ਉਦਾਹਰਣ

ਜਦੋਂ ਇੱਕ dynamic array ਭਰ ਜਾਂਦਾ ਹੈ, ਇਹ ਇੱਕ ਨਵਾਂ array allocate ਕਰਦਾ ਹੈ (ਆਮ ਤੌਰ ਉੱਤੇ **2×**) ਅਤੇ ਸਾਰੇ elements ਦੀ ਕਾਪੀ ਕਰਦਾ ਹੈ — ਇੱਕ O(n) ਕਦਮ। ਪਰ ਕਿਉਂਕਿ capacity **ਦੁਗਣੀ** ਹੋਵੇ ਜਾਂਦੀ ਹੈ, ਮਹਿੰਗੀਆਂ ਕਾਪੀਆਂ ਤੇਜ਼ੀ ਨਾਲ ਬਹੁਤ ਘੱਟ ਬਾਰ ਹੁੰਦੀਆਂ ਹਨ।

```text
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...
```

## ਗਣਿਤ

```text
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)
```

```python
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)** |

## ਡਬਲਿੰਗ ਕਿਉਂ (+1 ਨਹੀਂ)

**ਸਥਿਰ ਮਾਤਰਾ** ਨਾਲ ਵਧਣ ਨਾਲ ਹਰ insert ਇੱਕ copy trigger ਕਰੇਗਾ, O(n) amortized ਦੇਵੇਗਾ। Multiplicative ਵਾਧਾ ਹੀ ਸੋ ਕਰ ਲਾਗਤ ਫੈਲਾ ਦਿੰਦਾ ਹੈ।

## ਇਹ ਕਿਉਂ ਮਾਇਨੇ ਰੱਖਦਾ ਹੈ

Amortized ਵਿਸ਼ਲੇਸ਼ਣ ਪ੍ਰਦਰਸ਼ਨ ਦੀ ਇੱਕ ਨਿਰਪੱਖ, ਵਾਸਤਵਿਕ ਤਸਵੀਰ ਦਿੰਦਾ ਹੈ — ਇਸ ਤੋਂ ਬਿਨਾਂ, ਤੁਸੀਂ ਗਲਤ ਤਰੀਕੇ ਨਾਲ ਡਰੋਗੇ ਕਿ ਹਰ `append` ਜਾਂ hash-table insert O(n) ਹੈ।

ਇਹ ਇੱਕ ਮੁੱਖ design ਨਿਯਮ ਨੂੰ ਵੀ ਜਾਇਜ਼ ਠਹਿਰਾਉਂਦਾ ਹੈ: **capacity multiplicatively ਵਧਾਓ**, ਜੋ dynamic arrays, hash tables, ਅਤੇ string builders ਸਮੁੱਚੇ ਵਿੱਚ ਬਣਿਆ ਹੋਇਆ ਹੈ।