Complexité Amortie des Tableaux Dynamiques

1. Le Tableau Dynamique et le Problème du Coût

Un tableau dynamique (connu sous le nom de list en Python, ArrayList en Java, ou std::vector en C++) est une structure de données qui se comporte comme un tableau mais qui peut grandir dynamiquement.

La stratégie d'insertion est la suivante :

• On maintient un tableau interne d'une certaine capacité et on suit le nombre d'éléments réellement stockés.
• Si le tableau n'est pas plein, on ajoute le nouvel élément à la fin. C'est une opération rapide, en $O(1)$.
• Si le tableau est plein, on déclenche un redimensionnement avant d'insérer :
  1. On alloue un nouveau tableau, typiquement de taille double.
  2. On copie tous les éléments de l'ancien tableau vers le nouveau. Cette étape est coûteuse : $O(N)$ où $N$ est le nombre d'éléments.
  3. On ajoute le nouvel élément.

Cette alternance entre opérations très rapides et une opération ponctuellement très lente est le scénario idéal pour l'analyse amortie.

2. Qu'est-ce que la Complexité Amortie ?

L'analyse amortie consiste à déterminer le coût moyen d'une opération sur une séquence d'opérations, dans le pire des cas. Elle permet de lisser les pics de coûts.

Attention à ne pas la confondre avec l'analyse en cas moyen, qui repose sur des hypothèses probabilistes sur la distribution des données en entrée. L'analyse amortie, elle, ne fait aucune hypothèse probabiliste et garantit la performance sur n'importe quelle séquence d'opérations.

Pour la calculer, nous disposons de trois méthodes principales :

1. La méthode de l'agrégat
2. La méthode comptable
3. La méthode du potentiel

Nous allons explorer ces trois méthodes en les appliquant à notre problème de tableau dynamique. Je vous propose de commencer par une ressource en français, rédigée pour la préparation à l'Agrégation, qui expose brillamment l'analyse sur cet exemple.

En complément, la vidéo suivante offre une perspective visuelle et très didactique des trois mêmes méthodes.

Maintenant, synthétisons ce que ces ressources nous apprennent.

3. Les Trois Méthodes en Action

a) Méthode de l'Agrégat

L'idée est simple : calculer le coût total $T(n)$ d'une séquence de $n$ opérations dans le pire des cas, puis diviser par $n$ pour obtenir le coût amorti.

$\text{Couˆt amorti}=\frac{T(n)}{n}$

Considérons une séquence de $n$ insertions dans un tableau initialement vide qui double de taille.

• Une insertion a un coût de 1 si le tableau n'est pas plein.
• La $i$-ème insertion a un coût de $i$ ($1$ pour l'insertion elle-même + $i-1$ pour la copie) si elle déclenche un redimensionnement. Cela se produit lorsque $i-1$ est une puissance de 2 (en partant de la taille 1).

Le coût total pour $n$ insertions est la somme des coûts de toutes les insertions "simples" et des coûts de toutes les insertions "coûteuses" (avec redimensionnement).

Une analyse plus simple, comme dans la note de l'ENS, consiste à majorer le coût total :

La somme est une série géométrique : ${\sum }_{j=0}^k{2}^j=2^{k+1}-1$. Comme $2^{\lfloor {\log }_{2}n\rfloor }\le n$, la somme est inférieure à $2n$.
Donc, $T(n)\le n+2n=3n$.
Le coût total est en $O(n)$. Le coût amorti par opération est donc $O(n)/n=O(1)$.

b) Méthode Comptable

Cette méthode utilise une analogie financière. On assigne un coût amorti (ou "paiement") à chaque opération.

• Si le paiement est supérieur au coût réel, on stocke la différence ("crédit") dans une "banque".
• Si le paiement est inférieur au coût réel, on utilise le crédit accumulé pour combler le déficit.

La règle d'or est que le solde de la banque ne doit jamais être négatif.

Pour notre tableau dynamique :

• Assignons un coût amorti de 3 "pièces" à chaque insertion.
• Cas 1 : Pas de redimensionnement. Le coût réel est de 1 pièce. On paie 1 pièce pour l'insertion et on dépose les 2 pièces restantes en banque.
• Cas 2 : Redimensionnement. Supposons que le tableau passe de la taille $m$ à $2m$. Cela signifie que le tableau est plein et contient $m$ éléments. Le coût réel est de $m+1$ (copier $m$ éléments et en insérer un nouveau).
  • D'où vient l'argent pour payer ces $m$ copies ? Depuis le dernier redimensionnement (de $m/2$ à $m$), on a inséré $m/2$ éléments. Chacun a déposé 2 pièces en banque.
  • Nous avons donc $m/2\times 2=m$ pièces en banque.
  • Ces $m$ pièces paient exactement pour la copie des $m$ éléments. La pièce "courante" de notre paiement de 3 paie pour l'insertion elle-même. Les 2 autres pièces sont déposées pour un futur redimensionnement.

Le solde ne devient jamais négatif. Puisque nous avons trouvé un coût amorti constant (3) pour chaque opération, la complexité amortie est de $O(1)$.

c) Méthode du Potentiel

Cette méthode est une version plus formelle de la méthode comptable. Au lieu de crédits, on définit une fonction de potentiel $\Phi$ qui associe un nombre réel (le "potentiel") à chaque état de la structure de données.

Le coût amorti $\widehat{c_i}$ de la $i$-ème opération est défini par :
$\widehat{c_i}=c_i+\Phi (D_i)-\Phi (D_{i-1})$
où $c_i$ est le coût réel, $D_{i-1}$ est l'état avant l'opération, et $D_i$ est l'état après. $\Phi (D_i)-\Phi (D_{i-1})$ est la variation de potentiel.

On doit choisir $\Phi$ telle que :

1. $\Phi (D_0)=0$ pour l'état initial.
2. $\Phi (D_i)\ge 0$ pour tout état $i$.

Pour le tableau dynamique, une fonction de potentiel efficace est :
$\Phi (T)=2\cdot \text{T.num}-\text{T.capacity}$
où T.num est le nombre d'éléments et T.capacity la capacité du tableau.

• Vérifions les conditions : Pour une table vide, $\text{num}=0,\text{capacity}=0$, donc $\Phi =0$. Juste après un doublement, $\text{num}=\text{capacity}/2$, donc $\Phi =2\cdot (\text{capacity}/2)-\text{capacity}=0$. Entre deux redimensionnements, $\text{num}$ augmente, et on peut montrer que $\Phi \ge 0$ toujours.

Calculons le coût amorti :

• Cas 1 : Pas de redimensionnement.

  • Coût réel $c_i=1$.
  • ${\text{num}}_i={\text{num}}_{i-1}+1$, ${\text{capacity}}_i={\text{capacity}}_{i-1}$.
  • $\Delta \Phi =(2{\text{num}}_i-{\text{capacity}}_i)-(2{\text{num}}_{i-1}-{\text{capacity}}_{i-1})=2({\text{num}}_{i-1}+1)-2{\text{num}}_{i-1}=2$.
  • $\widehat{c_i}=1+2=3$.

• Cas 2 : Redimensionnement.

  • ${\text{num}}_{i-1}={\text{capacity}}_{i-1}=m$. Le coût réel $c_i=m+1$.
  • ${\text{num}}_i=m+1$, ${\text{capacity}}_i=2m$.
  • ${\Phi }_{i-1}=2m-m=m$.
  • ${\Phi }_i=2(m+1)-2m=2$.
  • $\Delta \Phi =2-m$.
  • $\widehat{c_i}=(m+1)+(2-m)=3$.

Dans les deux cas, le coût amorti est constant. La complexité amortie est donc de $O(1)$. Pour une présentation formelle de ces calculs, je vous encourage à consulter la ressource LINK (MIT OpenCourseWare).

Conclusion

Aujourd'hui, nous avons ajouté un outil puissant à votre arsenal d'analyste d'algorithmes. L'analyse amortie nous permet d'obtenir une vision plus juste de la performance des structures de données dynamiques, en évitant le pessimisme de l'analyse du pire cas sur une seule opération.

Points clés à retenir :

• La complexité amortie analyse le coût moyen d'une opération sur une séquence dans le pire des cas, et n'est pas de nature probabiliste.
• Le tableau dynamique, avec sa stratégie de doublement de capacité, est l'exemple canonique.
• Les trois méthodes (agrégat, comptable, potentiel) sont trois perspectives différentes qui mènent à la même conclusion rigoureuse : l'insertion dans un tableau dynamique a un coût amorti de $O(1)$.

Dans notre prochaine leçon, nous entamerons un nouveau module fondamental : les algorithmes de tri. Nous commencerons par l'un des plus simples, le tri par insertion, et analyserons sa complexité dans le meilleur et le pire des cas, ce qui nous ramènera à l'analyse plus classique d'une seule opération.