Accueil › Python › Complexité : ce que coûtent vraiment les opérations Python
Complexité : ce que coûtent vraiment les opérations Python
Algorithmique d'entretienavance
La complexité répond à une question : quand l'entrée double, le travail fait quoi ? O(1) ne bouge pas, O(n) double, O(n²) quadruple.
Mais en Python, la vraie compétence d'entretien n'est pas de savoir calculer un O() — c'est de connaître le coût des opérations qu'on écrit sans y penser. Les voici.
| Opération | Coût | Le piège |
|---|---|---|
t[i], len(t) |
O(1) | — |
t.append(x) |
O(1) amorti | — |
t.pop() |
O(1) | — |
t.pop(0), t.insert(0, x) |
O(n) | décale tout le reste |
x in t (liste) |
O(n) | compare un par un |
x in d, x in s (dict, set) |
O(1) moyen | — |
t.remove(x) |
O(n) | cherche, puis décale |
t[i:j] |
O(j - i) | copie |
sorted(t), t.sort() |
O(n log n) | O(n) si déjà trié |
s += autre dans une boucle |
O(n²) en principe | "".join(...) est en O(n) |
d.popleft() sur un deque |
O(1) | deque[n // 2] est O(n) |
heapq.heappush / heappop |
O(log n) | heapify est O(n) |
min(t), max(t), sum(t) |
O(n) | — |
Les deux lignes en gras sont celles qui font échouer les candidats. Elles ont la même cause : une liste Python est un tableau contigu. Ajouter à la fin est immédiat, toucher au début oblige à déplacer tout le reste.
# O(n²) — et aucune boucle imbriquée visible
vus = []
for c in commandes:
if c in vus: # O(n) à chaque tour
...
vus.append(c)
# O(n) — un seul mot a changé
vus = set()
for c in commandes:
if c in vus: # O(1) en moyenne
...
vus.add(c)
Les termes à connaître
- Notation O() (grand O)
Décrit comment le travail grossit quand l'entrée grossit, en ignorant les constantes et les termes non dominants.
3n + 500est O(n) ;n² + nest O(n²). Elle ne dit rien du temps en secondes, seulement de la forme de la croissance.- Coût amorti
Coût moyen par opération sur une longue suite d'opérations.
list.appendest amorti O(1) : la liste réserve plus de place qu'il n'en faut, donc la plupart des ajouts sont immédiats et la recopie occasionnelle se répartit sur tous les précédents.- Hachage
Ce qui rend
dictetsetrapides : la clé est transformée en un nombre qui désigne directement son emplacement. D'où le O(1) en moyenne dein,getetadd— contre O(n) sur une liste, qui doit comparer élément par élément.- Tranche (slice)
t[i:j]ne pointe pas dans la liste : elle en copie les éléments. Le coût est O(j - i), en temps comme en mémoire. Une tranche prise à chaque tour d'une boucle transforme un O(n) en O(n²).- Timsort
L'algorithme de
list.sortetsorted: O(n log n) dans le pire cas, mais O(n) sur une liste déjà triée ou presque, car il détecte les suites déjà ordonnées. Il est aussi stable : deux éléments égaux gardent leur ordre d'origine.- Complexité en espace
La mémoire supplémentaire utilisée, hors entrée. Un générateur travaille en O(1) d'espace là où la compréhension de liste équivalente consomme O(n) : c'est souvent ce qui distingue deux solutions de même complexité en temps.
- Facteur constant
Ce que O() ignore et que la machine paie quand même. Une boucle Python interprétée et un
sum()natif sont tous deux O(n), mais le second fait son travail dans du code compilé. À complexité égale, préférez la fonction intégrée.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.