 | Le type list python ne correspond pas au type de donnée abstrait liste étudié dans ce cours. |
Néanmoins il est intéressant de connaitre la complexité des méthodes telles qu'elles existent dans python.
Complexité de len(lst)
Commençons par la méthode len(), qui dans le type abstrait est considérée comme O(n)
Vous obervez que le temps d'exécution ne dépend finalement pas du nombre d'élément, il est constant. La raison est que l'objet list en python dispose d'un attribut qui stocke la longueur de la liste (on l'incrémente quand on ajoute un élément, on décrément quand on en retire un etc...). En conséquence l'appel à len(lst) est en O(1).
La méthode insert des listes de python
Nous n'avons pas implémenté la méthode insert() mais nous aurions put le faire, tout comme nous avons implémenté d'autres fonctions dérivées (appartient, lire_index, longueur...)
Il est bien d'avoir à l'esprit quelques notions sur les complexité de certaines opérations, et notament insert() : pour insérer un élément, par exemple à l'indice i, il faut décaler vers la droite tout les éléments qui était de l'indice i jusqu'à la fin. si on insère en début de la liste il faudra donc décaler tout les élements.....
observons le comportement de insert dans python d'abord une insertion en tête de liste :
En si on insère en queue de liste :
