Comment la structure du code révèle la complexité

Comment identifier Big O à partir du code

Big O se cache dans la forme de votre code. Quatre modèles couvrent la plupart des cas :

Boucle unique sur N éléments : O(N)

# O(N): one pass through the list
for item in list_of_n_items:
    process(item)

Boucles imbriquées, chacune sur N éléments : O(N²)

# O(N²): every item paired with every other item
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

Recherche en temps constant : O(1)

Accès par index de tableau, recherche dans une table de hachage — une étape quel que soit la taille.

Diviser pour régner (couper le problème en deux à chaque étape) : O(log N)

Recherche binaire : chaque vérification réduit de moitié les éléments restants.

---

O(N²) caché : une liste à l'intérieur d'une boucle

# This looks like O(N) but it is actually O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # scans all of visited: O(N)
        visited.append(item)  # the whole loop: O(N²)

La ligne if item not in visited scanne chaque élément de visited à chaque itération. Un scan de liste coûte O(N). Une boucle qui s'exécute N fois, faisant O(N) travail chacun : O(N) × O(N) = O(N²).

Ce modèle apparaît dans 1 000+ projets open-source. La correction prend un caractère : remplacez visited = [] par visited = set(). Les tests d'appartenance à un ensemble coûtent O(1), pas O(N). Un changement. Mêmes résultats. 1 000× plus rapide à N=1 000.

Classer et corriger ce code

Lisez ce code :

result = []
for name in student_names:
    if name not in result:
        result.append(name)

La théorie rencontre la pratique

Big O dans la réalité

Big O n'est pas juste une théorie. Il sépare les programmes qui se terminent en secondes des programmes qui prennent 17 minutes — sur exactement la même tâche.

Exemple réel : détection de cycle de dépendance dans un système de compilation.

Quand vous installez un logiciel, votre ordinateur résout un graphe de dépendances : le paquet A a besoin de B, B a besoin de C, et ainsi de suite. Un système de compilation vérifie ce graphe pour les cycles.

Un algorithme de détection de cycle O(N²) fonctionne bien à N=100 paquets. À N=50 000 paquets (un projet réel) : cela prend 17 minutes. La correction O(N) : 10 secondes.

Ce défaut exact existe dans GHC (compilateur Haskell), pip (gestionnaire de paquets Python), Maven (système de compilation Java), Cargo (gestionnaire de paquets Rust), & 1 000+ autres projets.

Pas parce que leurs auteurs étaient négligents. visited = [] a été écrit quand N était petit. Le code s'est calcifié. N a grandi. Personne n'a remarqué jusqu'à ce que la compilation prenne une demi-heure.

Big O est le vocabulaire qui vous permet de nommer ce qui s'est passé — & de le corriger.

---

Voulez-vous aller plus loin ? Notre cours unhamming inclut un chapitre complet sur Big O, MOAD-0001 (un vrai défaut O(N²) trouvé dans 1 000+ projets open-source), & pourquoi nommer un motif vous permet de le trouver partout. Voir The Missing Chapter: Algorithmic Complexity.

Prédire les temps de compilation

Un système de compilation utilise la détection de cycle O(N²).

Temps de compilation mesurés :

- N=100 paquets : 0,01 secondes

- N=1 000 paquets : 1 seconde

Pour O(N²) : le temps se met à l'échelle selon (N_new / N_old)².

Pour O(N) : le temps se met à l'échelle selon (N_new / N_old).