Chez Olympp, on aime quand le code tourne vite, proprement, et sans mauvaises surprises en production. Aujourd'hui, on s'attaque à une question décisive pour la performance de vos systèmes : combien de temps votre code met-il à faire son travail, et comment ce temps évolue quand les données grossissent ? C'est tout l'enjeu de la complexité algorithmique, souvent résumée par sa notation savante : le fameux « Big O ». Petite précaution d'usage : ce guide est volontairement imagé et simplifie certaines réalités plus complexes, le tout pour rester concis et accessible. Si un sujet vous accroche, n'hésitez pas à creuser au-delà de cet article.  

On ne compte pas des secondes

Premier réflexe à désamorcer : non, la complexité algorithmique ne se mesure pas en secondes. Pourquoi ? Parce que les secondes dépendent de la machine. Un même code tournera plus vite sur un serveur récent que sur un vieux portable. Mesurer en secondes, ce serait évaluer un coureur en fonction de la qualité de ses chaussures plutôt que de sa foulée. Ce qu'on veut mesurer, c'est quelque chose de plus profond et de propre à l'algorithme lui-même : combien d'opérations il effectue, et surtout comment ce nombre grandit quand la quantité de données augmente. On note cette quantité de données n. Et toute la question devient : quand n double, qu'arrive-t-il à mon temps de calcul ?  

Le monde merveilleux des courbes

Voici les grandes familles que vous croiserez au quotidien, de la meilleure à la pire.  

O(1) — le temps constant

Le rêve. Peu importe la taille des données, le coût reste le même. Accéder à la case 500 d'un tableau ne coûte pas plus cher que la case 2 : on calcule l'adresse, on lit, c'est fini. Que le tableau contienne 10 ou 10 millions d'éléments ne change rien. Analogie : appuyer sur l'interrupteur de la pièce. Que la maison fasse 30 m² ou 800 m², le geste prend le même temps.  

O(n) — le temps linéaire

Le coût grandit proportionnellement aux données. Deux fois plus de données, deux fois plus de travail. C'est ce qui se passe quand on parcourt une liste du début à la fin pour, par exemple, trouver une valeur ou calculer une somme. Analogie : vérifier une à une les enveloppes d'une pile de courrier pour retrouver une facture précise. Deux fois plus d'enveloppes, deux fois plus de temps.  

O(log n) — le temps logarithmique

Voici un excellent élève. Ici, doubler les données n'ajoute presque rien au coût. La courbe s'aplatit très vite. Le secret ? À chaque étape, on élimine la moitié des possibilités restantes. Analogie : chercher un mot dans un dictionnaire papier. Vous ne lisez pas page après page. Vous ouvrez au milieu, vous voyez si votre mot est avant ou après, et vous jetez d'un coup la moitié du dictionnaire. Puis vous recommencez. Un dictionnaire deux fois plus épais ne demande qu'une seule étape de plus. C'est exactement le principe de la recherche dichotomique.  

O(n log n) — le bon compromis

Un cran au-dessus du linéaire, mais ça reste très raisonnable. C'est la complexité des bons algorithmes de tri. Quand vous voyez n log n, dites-vous généralement : « OK, c'est du sérieux, c'est bien optimisé. »  

O(n²) — le temps quadratique

Là, ça se gâte. Doubler les données quadruple le travail. La courbe grimpe vite. Le coupable le plus fréquent : la boucle imbriquée. Une boucle dans une boucle, où chaque élément est comparé à tous les autres. Analogie : dans une soirée, chaque invité serre la main de chaque autre invité. À 10 personnes, c'est gérable. À 100, le nombre de poignées de main explose. À 1 000, la soirée est finie avant les présentations.  

O(2ⁿ) et O(n!) — les catastrophes

On les mentionne surtout pour que vous puissiez fuir en les reconnaissant. Ici, ajouter un seul élément peut doubler (voire pire) le temps de calcul. Quelques dizaines d'éléments suffisent à faire ramer un superordinateur pendant des années. Si votre solution tombe dans cette catégorie, c'est presque toujours le signe qu'il existe une bien meilleure approche à trouver.  

La grande règle : les constantes ne comptent pas

Voici le point qui surprend, et qu'il faut vraiment intégrer. En complexité algorithmique, on ignore les constantes et les détails. Un algorithme qui fait 2n opérations et un autre qui en fait 5n + 100 sont tous les deux considérés comme du O(n). On ne garde que le terme qui domine quand n devient grand. Pourquoi cette apparente désinvolture ? Parce que sur de gros volumes, c'est la forme de la courbe qui décide de tout, pas les petits écarts. Prenons un O(n) un peu lourd contre un O(n²) « léger ». Pour 5 éléments, le O(n²) peut très bien gagner. Mais à 10 000 éléments ? Le O(n) écrase tout, sans discussion. La nature de la croissance finit toujours par l'emporter sur les constantes. Attention, le piège inverse existe aussi : ne tombez pas dans l'excès d'optimisation. Pour cinq éléments traités une fois au démarrage, ne passez pas trois jours à optimiser une complexité. Le bon réflexe, c'est de repérer les portions de code qui tournent sur de gros volumes — c'est là que la complexité fait la différence.  

Quelques réflexes très concrets

La théorie, c'est bien. Voici comment elle se traduit au clavier.

• Méfiez-vous de la boucle dans la boucle. Dès que vous imbriquez deux parcours sur les mêmes données, une petite alarme doit sonner : vous êtes probablement en O(n²). Souvent, on peut l'éviter.
• Choisissez la bonne structure de données. Chercher un élément dans une liste classique, c'est du O(n) : on parcourt tout. Le chercher dans un dictionnaire / table de hachage (Dictionary, HashSet…), c'est du O(1) : un accès quasi direct. Changer de structure peut transformer un code lent en code instantané, sans toucher à la logique métier.
• Demandez-vous toujours : « et si n était énorme ? » Votre code marche sur 100 lignes de test. Tiendra-t-il sur 10 millions de lignes en production ? La réponse se lit dans sa complexité, pas dans son chrono du jour.

 

En conclusion

Il resterait beaucoup à dire — la complexité en espace (la mémoire consommée par l'algorithme), les cas moyens contre les pires cas, l'amortissement — mais ce guide est déjà bien fourni. L'essentiel à retenir :

• On ne mesure pas des secondes, mais la façon dont le coût grandit avec les données (n).
• Connaître les grandes familles — O(1), O(log n), O(n), O(n log n), O(n²) — permet de jauger un algorithme d'un coup d'œil.
• À grande échelle, c'est la forme de la courbe qui décide, pas les constantes. La bonne structure de données est souvent votre meilleure alliée.

Chez Olympp, ce sont précisément ces fondamentaux qui font la différence entre un système qui « marche » sur l'environnement de test et un système qui tient la charge le jour où les utilisateurs affluent. Si vous souhaitez aller plus loin sur ces sujets — ou faire auditer la performance de vos applications — nos équipes à Neuilly-sur-Seine seront ravies d'en discuter. Bon code à toutes et à tous. 🚀