Introduction à la Notation Big O
La notation Big O décrit comment le temps d'exécution d'un algorithme croît avec la taille de l'entrée.
Exemples Courants
- O(1) : Temps constant. Accès à un élément par index dans une liste.
- O(n) : Temps linéaire. Recherche d'un élément dans une liste non triée.
- O(n²) : Temps quadratique. Double boucle (ex: tri à bulles).
- O(log n) : Temps logarithmique. Recherche binaire dans une liste triée.
- O(n log n) : Temps linéarithmique. Tri fusionné (merge sort).
Pourquoi Ça Matière
Pour un ensemble de 1 million d'éléments, un algorithme O(n) prend ~1 seconde, tandis qu'un O(n²) prend ~11 jours !
— Fin —
← Retour au journal
