Performances des structures☘
Le tableau ci-dessous résume les performances moyennes (complexité en temps) attendues pour chacune des structures précédentes.
| Tableau | Pile | File | Liste | Tableau associatif |
|
|---|---|---|---|---|---|
| Nombre d'éléments | O(1) | O(n) | O(n) | O(n) | N.A. |
Valeur de l’élément d’indice i |
O(1) | O(n) | O(n) | O(n) | N.A. |
Modifier l’élément d’indice i |
O(1) | O(n) | O(n) | O(n) | N.A. |
| Insérer un élément en première position | O(n) | O(1) | O(n) | O(1) | N.A. |
| Insérer un élément en dernière position | O(n) | O(n) | O(1) | O(n) | N.A. |
| Insérer un élément en général | O(n) | O(1) | O(1) | O(1) | O(1) |
| Supprimer un élément en première position | O(n) | O(1) | O(1) | O(1) | N.A. |
| Supprimer un élément en dernière position | O(n) | O(n) | O(n) | O(n) | N.A. |
| Supprimer un élément en général | O(n) | O(1) | O(1) | O(1) | O(1) |
| Rechercher un élément de clé connue | N.A. | N.A. | N.A. | N.A. | O(1) |
| Rechercher une valeur connue | O(n) | O(n) | O(n) | O(n) | O(n) |
Remarques
-
Ce sont des moyennes.
Dans le pire des cas, les tableaux associatifs ont une complexité en O(n) pour l’insertion, la suppression et la recherche d’élément. -
Il existe des implémentations qui combinent le meilleur de chaque structure et peuvent améliorer ces performances.
On peut citer le typelisten Python, ou bien une implémentation de file avec des listes chaînées circulaires par exemple.