La complexité : pourquoi certains programmes explosent

Le problème : « ça marche chez moi »

Un programme qui répond en une seconde avec 100 données peut mettre des heures avec un million. Mesurer le temps sur ta machine ne suffit pas : ce temps dépend de l’ordinateur. La complexité algorithmique mesure autre chose : comment le nombre d’opérations grandit quand la taille n des données grandit.

Les grandes familles

• O(1) — constant : lire liste[5]. Le temps ne dépend pas de n.
• O(log n) — logarithmique : chercher dans une liste triée en la coupant en deux à chaque étape. 1 million d’éléments ≈ 20 étapes.
• O(n) — linéaire : parcourir toute la liste une fois. Dix fois plus de données, dix fois plus de temps.
• O(n log n) — les bons tris (tri fusion, tri rapide en moyenne).
• O(n²) — quadratique : deux boucles imbriquées (comparer chaque élément avec tous les autres). Dix fois plus de données, cent fois plus de temps.
• O(2ⁿ) — exponentiel : inutilisable dès que n dépasse quelques dizaines.

Déplace le curseur pour faire varier n et compare le nombre d’opérations de chaque famille.

Compter les opérations sur du vrai code

def contient(liste, cible):          # O(n)
    for x in liste:
        if x == cible:
            return True
    return False

def a_un_doublon(liste):             # O(n²)
    for i in range(len(liste)):
        for j in range(i + 1, len(liste)):
            if liste[i] == liste[j]:
                return True
    return False

def a_un_doublon_rapide(liste):      # O(n) grâce à un ensemble
    vus = set()
    for x in liste:
        if x in vus:
            return True
        vus.add(x)
    return False

import time
data = list(range(3000))
for f in (a_un_doublon, a_un_doublon_rapide):
    t = time.time()
    f(data)
    print(f.__name__, round((time.time() - t) * 1000, 1), "ms")

Les deux fonctions font le même travail. La seconde échange un peu de mémoire (l’ensemble vus) contre un gain de temps énorme : c’est le compromis temps / mémoire, omniprésent en informatique.

Comment lire une complexité

1. Une boucle sur n éléments → O(n).
2. Deux boucles imbriquées sur n → O(n²).
3. Deux boucles l’une après l’autre → O(n) + O(n) = O(n) : on ignore les constantes.
4. Un problème coupé en deux à chaque étape → O(log n).