Junior
Quelle est la complexité asymptotique des opérations sur les éléments dans la liste?
sobes.tech IA
Réponse de l'IA
Cela dépend du type de liste et de l'opération.
On considère généralement les types de listes suivants :
- Liste simplement chaînée
- Liste doublement chaînée
- Tableau (cas particulier de liste)
Opérations :
- Accès par index
- Insertion
- Suppression
- Recherche de valeur
| Opération | Liste simplement chaînée | Liste doublement chaînée | Tableau |
|---|---|---|---|
| Accès par index | O(n) | O(n) | O(1) |
| Insertion | O(1) (au début) | O(1) (au début/fin) | O(n) |
| Suppression | O(n) | O(n) | O(n) |
| Recherche de valeur | O(n) | O(n) | O(n) |
Explications :
- O(1) (temps constant) : L'opération prend un temps fixe, indépendamment de la taille de la liste. Par exemple, accéder à un élément par index dans un tableau.
- O(n) (temps linéaire) : Le temps d'exécution de l'opération est proportionnel à la taille de la liste. Par exemple, rechercher un élément dans une liste non triée.
- O(log n) (temps logarithmique) : Le temps d'exécution augmente logarithmiquement avec la taille de la liste. Souvent rencontré lors de la manipulation de données triées (par exemple, recherche binaire).
Détails :
- Dans une liste simplement chaînée : insertion en début - O(1). Insertion en fin ou insertion/suppression par index nécessite de parcourir la liste jusqu'à l'élément souhaité, ce qui donne O(n).
- Dans une liste doublement chaînée : insertion en début et en fin - O(1). Insertion/suppression à une position donnée - O(1), mais recherche de ce nœud par valeur ou index - O(n).
- Dans un tableau : accès par index - O(1). Insertion ou suppression au milieu du tableau nécessite de décaler les éléments, ce qui donne O(n). Insertion/suppression en fin, si une capacité est réservée (par exemple, dans
std::vectoravec une certaine capacité), peut être O(1) en moyenne, mais O(n) dans le pire cas (réallocation).