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) |