Complexité et notation grand O

Deux programmes peuvent donner le même résultat et pourtant se comporter très différemment : l’un répond en un clin d’œil sur un million de lignes, l’autre tourne pendant des heures. La complexité permet de prévoir ce comportement avant de lancer le code.

Compter les opérations

On ne mesure pas des secondes (qui dépendent de la machine) mais le nombre d’opérations élémentaires en fonction de la taille n de l’entrée.

def contient(liste, cible):
    for x in liste:          # au pire n tours
        if x == cible:       # 1 comparaison par tour
            return True
    return False

Au pire cas (élément absent), on fait n comparaisons : le coût est proportionnel à n.

def a_des_doublons(liste):
    n = len(liste)
    for i in range(n):              # n tours
        for j in range(i + 1, n):   # jusqu'à n - 1 tours
            if liste[i] == liste[j]:
                return True
    return False

Ici, on compare chaque paire : environ n²/2 comparaisons. Doubler la taille de la liste quadruple le temps.

La notation grand O

La notation O décrit l’ordre de grandeur de la croissance en gardant le terme dominant et en ignorant les constantes :

• 3n + 5 devient O(n) ;
• n²/2 + n devient O(n²) ;
• 10 opérations quel que soit n : O(1) (temps constant).

Pourquoi ignorer les constantes ? Parce que pour de grandes valeurs de n, c’est la forme de la courbe qui l’emporte : un algorithme O(n) finit toujours par battre un O(n²).

Les classes à connaître

Complexité	Nom	Exemple	n = 1 000 000
O(1)	constante	accès liste[i], clé de dictionnaire	1
O(log n)	logarithmique	recherche binaire	environ 20
O(n)	linéaire	parcourir une liste	10⁶
O(n log n)	quasi linéaire	trier avec sorted	environ 2 × 10⁷
O(n²)	quadratique	comparer toutes les paires	10¹²
O(2ⁿ)	exponentielle	tester tous les sous-ensembles	inenvisageable

À raison de cent millions d’opérations simples par seconde (ordre de grandeur pour du Python), 10¹² opérations prennent plusieurs heures.

Règles pratiques

• Des instructions à la suite : on additionne et on garde le plus gros terme (O(n) + O(n²) = O(n²)).
• Des boucles imbriquées : on multiplie (O(n) × O(n) = O(n²)).
• Diviser le problème par deux à chaque étape : O(log n).
• Attention aux opérations cachées : x in liste est O(n), donc une boucle qui fait if x in liste est O(n²).

Et la mémoire ?

La complexité spatiale mesure la mémoire supplémentaire utilisée. Créer une copie de la liste coûte O(n) en mémoire ; garder deux variables coûte O(1). On échange souvent de la mémoire contre du temps, comme nous le verrons avec les dictionnaires.

Vérifier par la mesure

import timeit
donnees = list(range(10_000))
t = timeit.timeit(lambda: contient(donnees, -1), number=100)
print(f"{t:.3f} s pour 100 recherches")

En doublant la taille et en observant le temps, vous confirmez l’analyse : temps doublé pour O(n), quadruplé pour O(n²).