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.

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).