Formations — 1 037 leçons en français

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 + 500 est O(n) ; n² + n est 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.append est 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 dict et set rapides : la clé est transformée en un nombre qui désigne directement son emplacement. D'où le O(1) en moyenne de in, get et add — 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.sort et sorted : 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.

Lire l'explication détaillée et faire le quiz →

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.