Što je amortizirana analiza, koristeći dinamičko promjenjivanje veličine niza kao primjer?

Question

Accepted Answer

**Amortizirana analiza** mjeri **prosječnu cijenu po operaciji tijekom niza**, čak i kada pojedine operacije povremeno koštaju mnogo više. Objašnjava zašto je `append` dinamičkog niza "**O(1) amortizirana**" unatoč povremenim O(n) promjenama veličine.

## Primjer dinamičkog niza

Kad se dinamički niz napuni, on alocira novi niz (obično **2×**) i kopira sve elemente — korak O(n). Ali jer se kapacitet **udvostručava**, skupo kopiranje postaje eksponencijalno rijeđe.

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

| Operacija | Najgori slučaj | Amortizirana |
|---|---|---|
| append (udvostručavanje) | O(n) | **O(1)** |

## Zašto udvostručavanje (ne +1)

Rastanje za **fiksni iznos** bi izazvalo kopiranje pri svakom unosu, dajući O(n) amortiziranu. Multiplikativni rast je ono što razmazuje cijenu.

## Zašto je važno

Amortizirana analiza daje fer, realističnu sliku performansi — bez nje, pogrešno biste se bojali da je svaki `append` ili ubacivanje u hash-tablicu O(n).

Također opravdava ključno pravilo dizajna: **povećaj kapacitet multiplikativno**, što leži u temelju dinamičkih nizova, hash-tablica i string graditelja svugdje.