Amortized analysis म्हणजे काय? Dynamic array resizing चे उदाहरण वापरून समजावा.

Question

Accepted Answer

**Amortized analysis** हे **एका क्रमाच्या ऑपरेशन्सवर सरासरी खर्च** मापन करते, भरपूर वेळा वैयक्तिक ऑपरेशन्स खूपच अधिक खर्चिक असतात हे असूनही. Dynamic array च्या `append` ला "**O(1) amortized**" का असे म्हणतात हे समजावते, जरी अखेरीस O(n) resizes होतात.

## Dynamic array चे उदाहरण

जेव्हा dynamic array भरून जाते, तेव्हा तो नवीन array allocate करतो (सामान्यत: **2×**) आणि सर्व elements copy करतो — हे एक O(n) step आहे. परंतु कारण capacity **दुप्पट** होते, महाग copies exponentially कमी होतात.

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

| Operation | सर्वात वाईट एकल | Amortized |
|---|---|---|
| append (doubling) | O(n) | **O(1)** |

## दुप्पट होणे का (फक्त +1 का नाही)

**स्थिर संख्या** ने वाढ केल्याने प्रत्येक insert एक copy trigger करेल, O(n) amortized देईल. Multiplicative growth हीच असली गोष्ट आहे जी खर्च पसरवते.

## हे महत्वाचे का आहे

Amortized analysis performance चे न्याय्य, वास्तविक चित्र देते — याशिवाय, तुम्ही चुकीने असा समजू शकता की प्रत्येक `append` किंवा hash-table insert हा O(n) आहे.

हे एका मुख्य डिজाइन नियमाला न्याय देते: **capacity multiplicatively वाढवा**, जे dynamic arrays, hash tables, आणि string builders सर्वत्र अंतर्भूत आहे.