Что такое амортизированный анализ на примере динамического изменения размера массива?

Question

Accepted Answer

**Амортизированный анализ** измеряет **среднюю стоимость операции в последовательности**, даже когда отдельные операции иногда обходятся намного дороже. Он объясняет, почему `append` динамического массива это "**O(1) амортизированная**" операция, несмотря на случайные изменения размера O(n).

## Пример динамического массива

Когда динамический массив заполняется, он выделяет новый массив (обычно **2×**) и копирует все элементы — шаг O(n). Но поскольку ёмкость **удваивается**, дорогостоящие копирования становятся экспоненциально редче.

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

## Математика

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

| Операция | Наихудший случай | Амортизированная |
|---|---|---|
| append (удвоение) | O(n) | **O(1)** |

## Почему удвоение (а не +1)

Рост на **постоянное значение** привел бы к тому, что каждая вставка вызывает копирование, что дает O(n) амортизированную сложность. Мультипликативный рост — это то, что распределяет затраты.

## Почему это важно

Амортизированный анализ дает объективную и реалистичную картину производительности — без него вы необоснованно боялись бы, что каждая `append` или вставка в хеш-таблицу это O(n).

Он также обоснует ключевое правило проектирования: **расширяй ёмкость мультипликативно**, которое лежит в основе динамических массивов, хеш-таблиц и построителей строк везде.