Apa iku amortized analysis, nggunakaken dynamic array resizing minangka contone?

Question

Accepted Answer

**Amortized analysis** ngukur **rata-rata biaya per operasi sajrone sequence**, sanajan operasi individual kadhang-kadhang biayane luwih dhuwur. Iki njlasake kenapa `append` dynamic array yaiku "**O(1) amortized**" senadyan ana O(n) resizes kadhang-kadhang.

## Contone dynamic array

Sawise dynamic array penuh, iku alokasi array anyar (biasane **2×**) lan nyalin kabeh element — langkah O(n). Nanging amarga capacity **mbur-mburu**, copy sing larang dadi luwih langka.

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

## Matematika

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

| Operasi | Paling akeh tunggal | Amortized |
|---|---|---|
| append (doubling) | O(n) | **O(1)** |

## Kenapa doubling (ora +1)

Growing kanthi **amount konstan** bakal gawe saben insert trigger copy, menehi O(n) amortized. Multiplicative growth yaiku apa kang nyebarake biaya.

## Apa pentinge

Amortized analysis menehi gambaran fair lan realistis babagan performa — tanpa iku, sampeyan bakal salah takut manawa saben `append` utawa hash-table insert yaiku O(n).

Iki uga njlasake peraturan desain kunci: **grow capacity multiplicatively**, kang ndasari dynamic arrays, hash tables, lan string builders ing mana-mana.