Co je amortizovaná analýza s použitím změny velikosti dynamického pole jako příkladu?

Question

Accepted Answer

**Amortizovaná analýza** měří **průměrné náklady na operaci v sekvenci**, i když jednotlivé operace příležitostně stojí mnohem více. Vysvětluje, proč je `append` dynamického pole "**O(1) amortized**" navzdory příležitostným O(n) změnám velikosti.

## Příklad dynamického pole

Když se dynamické pole zaplní, přidělí nové pole (obvykle **2×**) a zkopíruje všechny prvky — o(n) krok. Protože se kapacita **zdvojnásobuje**, drahé kopie se stávají exponenciálně vzácnějšími.

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

| Operace | Nejhorší případ | Amortizované |
|---|---|---|
| append (doubling) | O(n) | **O(1)** |

## Proč zdvojnásobení (ne +1)

Růst o **konstantní hodnotu** by vyvolal kopii při každém vložení, což dává O(n) amortizované. Multiplikativní růst je to, co rozprostírá náklady.

## Proč je to důležité

Amortizovaná analýza poskytuje spravedlivý a realistický obraz výkonu — bez ní byste se mylně obávali, že každé `append` nebo vložení do hash-tabulky je O(n).

Zároveň ospravedlňuje klíčové pravidlo návrhu: **zvětšit kapacitu multiplikativně**, což je základem dynamických polí, hash-tabulek a string builderů všude.