Qu'est-ce que la notation Big-O ?
La notation Big-O (ou notation asymptotique) décrit comment le temps d'exécution ou l'espace mémoire d'un algorithme évolue en fonction de la taille de l'entrée (n). Elle caractérise le comportement dans le pire cas quand n devient très grand. O(n) signifie que le temps croît linéairement avec la taille des données : doubler les données double le temps. O(n²) signifie que doubler les données quadruple le temps. Cette notation permet de comparer l'efficacité des algorithmes indépendamment du matériel.
Les complexités les plus courantes en pratique
En développement quotidien, vous rencontrez principalement O(1) pour l'accès en table de hachage, O(log n) pour la recherche binaire, O(n) pour le parcours de tableaux, O(n log n) pour les tris efficaces (merge sort, quick sort), et O(n²) pour les boucles imbriquées. La règle d'or : si votre algorithme a une complexité de O(n²) ou pire sur de grandes données, cherchez une meilleure approche. La plupart des problèmes courants ont une solution en O(n) ou O(n log n).
Comment analyser la complexité de votre code
Pour déterminer la complexité Big-O, identifiez les boucles : une boucle for sur n éléments est O(n), deux boucles imbriquées sont O(n²). Les appels récursifs qui divisent le problème en deux (dichotomie) sont O(log n). Les algorithmes diviser pour régner qui combinent division et itération (merge sort) sont O(n log n). Les constantes et termes inférieurs sont ignorés : O(3n + 5) se simplifie en O(n), O(n² + n) en O(n²). Seul le terme dominant compte pour les grandes valeurs de n.