Algorithmes qui finissent à temps : Un contrôle de réalité sur la complexité

Vous écrivez une fonction, la testez sur vos données de test, et ça marche bien. Ensuite, elle arrive en production — 500 000 lignes au lieu de 500 — et la requête expire. Cela arrive constamment, et c'est presque toujours un problème de complexité caché derrière du code qui semblait raisonnable à petite échelle.

Pourquoi votre laptop vous a menti

Un algorithme O(n²) exécuté sur 100 éléments effectue 10 000 opérations. C'est instantané sur n'importe quelle machine. Exécutez le même algorithme sur 100 000 éléments et vous êtes à 10 milliards d'opérations — des minutes ou des heures au lieu de millisecondes. Le passage de n à n² ne semble pas dangereux tant que n reste petit, ce qui est exactement pourquoi cela passe inaperçu lors de la revue de code et des tests locaux.

Un exemple classique : vérifier les doublons avec une boucle imbriquée.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

C'est O(n²). Remplacez-le par un set :

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

C'est maintenant O(n). Les recherches dans un set sont en moyenne O(1), donc toute la fonction évolue linéairement au lieu de quadratiquement. Sur 10 000 éléments, c'est la différence entre environ 100 millions de comparaisons et 10 000.

Mesurez avant d'optimiser

Ne deviquez pas. Utilisez timeit pour les microbenchmarks :

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Pour les fonctions plus grandes, profilez avec cProfile :

python -m cProfile -s cumulative myscript.py

Regardez la colonne cumtime. Si une fonction consomme 90 % du temps d'exécution, c'est votre cible. Optimiser du code qui n'est pas le goulot d'étranglement gaspille votre temps et ajoute de la complexité sans gain.

Les motifs courants qui deviennent lentement lents

Vérifications répétées d'appartenance à une liste. if x in my_list est O(n) pour une liste mais O(1) en moyenne pour un set ou un dict. Si vous vérifiez l'appartenance à l'intérieur d'une boucle, cette vérification O(n) à l'intérieur d'une boucle O(n) vous donne O(n²) globalement. Remplacez la liste par un set et vous êtes de retour à O(n).

Concaténation de chaînes dans une boucle. En Python, result += chunk à l'intérieur d'une boucle sur des chaînes est O(n²) au pire car les chaînes sont immuables et chaque concaténation copie le tout. Utilisez ''.join(chunks) à la place — cela construit la chaîne une seule fois.

Tri quand vous n'en avez pas besoin. sorted() est O(n log n). Si vous l'appelez à l'intérieur d'une boucle juste pour trouver le max ou le min à chaque itération, utilisez max()/min() (O(n)) ou mieux, un heap (heapq) si vous avez besoin de l'extrême courant à plusieurs reprises. heapq.nlargest(k, data) est O(n log k), beaucoup moins cher que de trier la liste entière quand k est petit.

Fonctions récursives sans mémoïsation. La suite de Fibonacci récursive naïve est O(2ⁿ) car elle recalcule les mêmes sous-problèmes encore et encore. Ajoutez functools.lru_cache et cela descend à O(n) :

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Lire Big O sur du vrai code, rapidement

Comptez les boucles imbriquées sur la même entrée — c'est généralement votre exposant. Une boucle unique est O(n). Une boucle à l'intérieur d'une boucle est O(n²) sauf si la plage de la boucle interne diminue (comme dans la forme optimisée du tri à bulles, toujours O(n²) au pire mais moins de comparaisons). Les appels récursifs qui divisent le problème en deux, comme la recherche binaire ou le tri fusion, pointent vers O(log n) ou O(n log n). Les appels récursifs qui se divisent en plusieurs appels par niveau, comme la suite de Fibonacci naïve, pointent vers un temps exponentiel — un signal fort que vous avez besoin de mémoïsation ou d'une réécriture itérative.

Une bonne habitude : avant d'écrire des boucles imbriquées ou de la récursion sur des données visibles par l'utilisateur, demandez-vous ce que n pourrait réalistically être en production, pas dans votre fichier de test. Si n pourrait atteindre six chiffres, une solution O(n²) a besoin d'un second regard avant qu'elle ne soit déployée.

Pour plus d'informations sur l'analyse de complexité, les algorithmes de tri et les outils de profiling, consultez les segments Python et Computer Science sur Korra Studio.