Mitä on amortisoidun analyysin analyysimenetelmä, käyttäen dynaamisen taulukon koon muuttamista esimerkkinä?

Question

Accepted Answer

**Amortisoidun analyysin** analyysimenetelmä mittaa **keskimääräisiä kustannuksia toimintoa kohti sarjassa**, vaikka yksittäiset toiminnot välillä maksavat paljon enemmän. Se selittää, miksi dynaamisen taulukon `append` on "**O(1) amortisoidusti**" huolimatta satunnaisista O(n)-kokoisuuden muutoksista.

## Dynaamisen taulukon esimerkki

Kun dynaaminen taulukko täyttyy, se kohdistaa uuden taulukon (tavallisesti **2×**) ja kopioi kaikki elementit — O(n)-vaihe. Mutta koska kapasiteetti **kaksinkertaistuu**, kalliin kopioinnit tulevat eksponentiaalisesti harvinaisemmiksi.

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

## Matematiikka

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

| Toiminto | Pahin yksittäinen | Amortisoidusti |
|---|---|---|
| append (doubling) | O(n) | **O(1)** |

## Miksi kaksinkertaistaminen (ei +1)

Kasvaminen **vakiotekijällä** laukaisisi kopioinnin jokaisessa lisäyksessä, antaen O(n) amortisoidusti. Multiplikatiivinen kasvu on se, joka levittää kustannukset.

## Miksi se on tärkeää

Amortisoidun analyysin analyysimenetelmä antaa reilun ja realistisen kuvan suorituskyvystä — ilman sitä, pelkäisit väärin, että jokainen `append` tai hash-taulukon lisäys on O(n).

Se myös perustelee keskeisen suunnittelusäännön: **kasvata kapasiteettia kertoimella**, joka on dynaamisten taulukoiden, hash-taulukoiden ja merkkijonojen rakentajien taustalla kaikkialla.