Qu'est-ce que l'analyse amortie, en utilisant le redimensionnement dynamique d'un tableau comme exemple ?

Question

Accepted Answer

**L'analyse amortie** mesure le **coût moyen par opération sur une séquence**, même lorsque certaines opérations individuelles coûtent bien plus cher. Elle explique pourquoi l'opération `append` d'un tableau dynamique est "**O(1) amorti**" malgré les redimensionnements occasionnels en O(n).

## Le tableau dynamique comme exemple

Quand un tableau dynamique est plein, il alloue un nouveau tableau (généralement **2×**) et copie tous les éléments — une étape en O(n). Mais comme la capacité **double**, les copies coûteuses deviennent exponentiellement plus rares.

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

## Les mathématiques

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

| Opération | Pire cas isolé | Amorti |
|---|---|---|
| append (doublement) | O(n) | **O(1)** |

## Pourquoi doubler (et non +1)

Croître d'une **quantité constante** ferait déclencher une copie à chaque insertion, donnant une amortie en O(n). La croissance multiplicative est ce qui étale le coût.

## Pourquoi c'est important

L'analyse amortie donne une image juste et réaliste de la performance — sans elle, vous craindriez à tort que chaque `append` ou insertion dans une table de hachage soit en O(n).

Elle justifie aussi une règle de conception clé : **croître la capacité multiplicativement**, ce qui sous-tend les tableaux dynamiques, les tables de hachage et les générateurs de chaînes partout.