Was ist amortisierte Analyse, am Beispiel der Größenänderung dynamischer Arrays?

Question

Accepted Answer

**Amortisierte Analyse** misst die **durchschnittlichen Kosten pro Operation über eine Sequenz**, auch wenn einzelne Operationen gelegentlich viel teurer sind. Sie erklärt, warum das `append` eines dynamischen Arrays "**O(1) amortized**" ist, obwohl gelegentliche O(n)-Größenänderungen stattfinden.

## Das Beispiel des dynamischen Arrays

Wenn ein dynamisches Array voll wird, reserviert es ein neues Array (üblicherweise **2×**) und kopiert alle Elemente — ein O(n)-Schritt. Aber da die Kapazität sich **verdoppelt**, werden teure Kopien exponentiell seltener.

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

## Die Mathematik

```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 | Schlimmster Fall | Amortisiert |
|---|---|---|
| append (doubling) | O(n) | **O(1)** |

## Warum Verdopplung (nicht +1)

Ein Wachstum um einen **konstanten Betrag** würde bei jedem Einfügen eine Kopie auslösen und O(n) amortisiert ergeben. Multiplikatives Wachstum ist das, was die Kosten verteilt.

## Warum es wichtig ist

Amortisierte Analyse gibt ein realistisches und gerechtes Bild der Leistung — ohne sie würde man fälschlicherweise befürchten, dass jedes `append` oder hash-table insert O(n) ist.

Sie rechtfertigt auch eine wichtige Designregel: **Kapazität multiplikativ wachsen lassen**, die dynamischen Arrays, Hash-Tabellen und String-Buildern überall zugrunde liegt.