Skip to content

Texte

Complexité des manipulations de séquences de données python

La complexité des manipulation des séquences de données sont dépendantes de l'implémentation de python utilisée.

Nous nous basons donc sur l'implémentation CPython utilisé au moins jusqu'à la version Python 3.10.

Dans ce qui suit, on suppose que \(n\) est le nombre d'éléments dans la séquence et \(k\) la valeur (ex: longueur) du paramètre.

La complexité moyenne suppose que les paramètres sont générés uniformément de façon aléatoire.

Complexité des opérations sur les listes

De façon interne, une liste est représentée sous forme de vecteur où les composantes sont contiguës en mémoire et avec, en moyenne, de la place libre pour allonger la liste. La pire opération est donc une insertion ou suppression en début de liste car toutes les composantes doivent bouger. Malheureusement, au pire des cas, un simple s.append(x) peut demander de recopier toute la liste s'il n'y a plus de place libre juste après la liste s.

Opération Complexité moyenne Complexité maximale
Copy O(n) O(n)
Append O(1) O(n)
Insert O(n) O(n)
Get Item O(1) O(1)
Set Item O(1) O(1)
Delete Item O(n) O(n)
Iteration O(n) O(n)
Get Slice O(k) O(k)
Del Slice O(n) O(n)
Set Slice O(k+n) O(n+k)
Extend O(k) O(n+k)
Sort O(n log n) O(n log n)
Multiply O(nk) O(nk)
x in s O(n) O(n)
min(s), max(s) O(n) O(n)
len(s) O(1) O(1)

Complexité des opérations sur les dictionnaires

Avec l'interpréteur que nous utilisons, un dictionnaire Python est stocké dans une table (zone mémoire contiguë). Pour simplifier supposant que c'est une table à MAX composantes (par exemple pour un petit dictionnaire MAX = 100.

L'accès à une composante du dictionnaire (Get Item) se fait par hashing (hash(cle) % 100) qui calcule un indice entre 0 et MAX-1. En moyenne cet indice correspond à l'emplacement dans la table où l'élément (clé et valeur) va être stocké. Cette opération (hashing, modulo et accès à la table) prend un temps constant O(1).

La complexité moyenne suppose que les collisions sont rares avec la fonction de hashage (ce qui est généralement la cas).

Le cas moyen suppose que les paramètres sont choisis uniformément aléatoirement parmi les clés possibles.

Malheureusement, il peut y avoir des collisions. Au pire des cas, pour un dictionnaire de néléments, l'accès à un élément aura n-1 collisions plus le dernier hashing et prend un temps (complexité maximale) en O(n).

En terme de complexité, placer un élément (Set Item) revient à y accéder suivit du stockage de l'élément qui est en O(1) en moyenne et O(n) en complexité maximale, soit la même complexité que l'accès à un élément.

Opération Complexité moyenne Complexité maximale
Copy O(n) O(n)
Get Item O(1) O(n)
Set Item O(1) O(n)
Delete Item O(1) O(n)
Iteration O(n) O(n)