Complexités des structures de données
IntermédiaireLe tableau à avoir en tête avant tout entretien : quelle structure pour quelle opération.
n est le nombre d'éléments.
| Structure | Accès | Recherche | Insertion | Suppression | Note |
|---|---|---|---|---|---|
| Tableau dynamique | O(1) | O(n) | O(1) amorti en fin, O(n) ailleurs | O(1) en fin, O(n) ailleurs | Trié : recherche binaire en O(log n) |
| Hashmap / Set | — | O(1) moyen | O(1) moyen | O(1) moyen | Pire cas O(n) en cas de collisions, pas d'ordre garanti |
| Liste chaînée | O(n) | O(n) | O(1) en tête ou sur un nœud connu | O(1) sur un nœud connu | Pas d'accès direct par index |
| Pile / File (deque) | — | O(n) | O(1) | O(1) | En Python, collections.deque pour une file |
| BST équilibré | — | O(log n) | O(log n) | O(log n) | Non équilibré : O(n) dans le pire cas |
| Heap | O(1) sur le min/max | O(n) | O(log n) | O(log n) sur le min/max | Construction depuis n éléments : O(n) |
| Trie | — | O(L) | O(L) | O(L) | L = longueur du mot, indépendant du nombre de mots |
Astuce : la question « laquelle choisir ? » se ramène presque toujours à : besoin d'un accès par clé (hashmap), de l'ordre (BST, tri), du min/max (heap), ou du dernier/premier arrivé (pile/file).