Complexité linéaire et quadratique
Pourquoi s'intéresser à la complexité ?
Quand on écrit un algorithme, il est important de savoir combien de temps il prendra pour s'exécuter et combien de mémoire il utilisera.
Pour cela, on étudie sa complexité en fonction de la taille des données à traiter, que l'on note souvent n.
La complexité donne une idée de l'évolution du temps d'exécution en fonction de la taille de l'entrée.
Complexité linéaire
Un algorithme est dit de complexité linéaire lorsqu'il effectue un nombre d'opérations proportionnel à la taille des données.
- Si on double la taille des données, le temps d'exécution double aussi.
- La complexité s'exprime alors par O(n).
Exemples :
- Parcourir une liste pour afficher tous ses éléments.
- Chercher un élément en testant un par un (recherche séquentielle).
Complexité quadratique
Un algorithme est dit de complexité quadratique lorsqu'il effectue un nombre d'opérations proportionnel au carré de la taille des données.
- Si on double la taille des données, le temps d'exécution est multiplié par 4.
- La complexité s'exprime alors par O(n²).
Exemples :
- Comparer tous les couples d'éléments dans une liste (ex : recherche de doublons naïve).
- Tri à bulles (bubble sort).
Un algorithme quadratique devient rapidement très lent pour de grandes données. On cherche donc à préférer des algorithmes de complexité plus faible (linéaire ou log-linéaire) lorsque c'est possible.