Comprendre et calculer le coût amorti des opérations de représentation dynamique

Les tableaux dynamiques sont des structures de données qui redimensionnent automatiquement leur capacité. Comprendre leur coût amorti aide à évaluer leur efficacité sur plusieurs opérations.

Qu'est-ce que le coût amorti?

Le coût amorti est le coût moyen par opération sur une séquence d'opérations. Il permet de réduire les coûts élevés de redimensionnement occasionnel en les distribuant dans de nombreuses opérations peu coûteuses.

Opérations d'array dynamique

Les opérations courantes sur les tableaux dynamiques comprennent l'insertion, la suppression et le redimensionnement. L'insertion à la fin est généralement l'opération la plus fréquente, qui peut déclencher le redimensionnement lorsque la capacité est dépassée.

Calcul du coût amorti

Lorsque vous insérez des éléments, le tableau double en taille lorsque vous en avez plein. Le coût de la redimensionnement implique de copier tous les éléments existants dans le nouveau tableau. Bien que la redimensionnement soit coûteux, il se produit rarement.

Par exemple, si un tableau commence par la capacité 1, la séquence des coûts de redimensionnement par rapport à plusieurs insertions peut être résumée comme suit :

• Insérer 1 élément: coût 1
• Insérer 2ème élément: redimensionner (coût 1), coût total 2
• Insérer 3ème élément: redimensionner (coût 2), coût total 3
• Insérer 4ème élément: redimensionner (coût 4), coût total 4

Le coût total des insertions sur n est proportionnel à 2n, ce qui fait que le coût amorti par insertion est d'environ O(1).