Hvad er amortiseret analyse, idet man bruger dynamisk array-ændring af størrelse som eksempel?

Question

Accepted Answer

**Amortiseret analyse** måler **den gennemsnitlige omkostning pr. operation over en sekvens**, selv når individuelle operationer lejlighedsvis koster meget mere. Det forklarer, hvorfor en dynamisk arrays `append` er "**O(1) amortized**" på trods af lejlighedsvise O(n) ændringer af størrelse.

## Det dynamiske array-eksempel

Når et dynamisk array bliver fuldt, tildeler det et nyt array (normalt **2×**) og kopierer alle elementer — et O(n) trin. Men fordi kapaciteten **fordobles**, bliver dyre kopier eksponentielt sjældnere.

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

## Matematikken

```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 | Værste enkelt | Amortiseret |
|---|---|---|
| append (doubling) | O(n) | **O(1)** |

## Hvorfor fordobling (ikke +1)

At vokse med et **konstant beløb** ville udløse en kopi ved hver indsættelse, hvilket giver O(n) amortiseret. Multiplikativ vækst er det, der spreder omkostningerne.

## Hvorfor det betyder noget

Amortiseret analyse giver et retfærdigt, realistisk billede af ydeevnen — uden det ville du forkert frygte, at hver `append` eller hash-table-indsættelse er O(n).

Det begrunder også en nøgle-designregel: **vokse kapaciteten multiplikativt**, som ligger bag dynamiske arrays, hash-tabeller og string-bygere overalt.