Complexité Algorithmique

• La complexité algorithmique mesure le temps et l'espace requis par un algorithme pour une entrée d'une taille donnée. Elle sert à comparer l'efficacité des algorithmes et à prédire leur scalabilité.

Expression de la complexité

• La notation Big O est utilisée pour exprimer la complexité.
• Elle décrit la limite supérieure du taux de croissance d'un algorithme, se concentrant sur le pire des cas.
• Les facteurs constants et les termes d'ordre inférieur sont ignorés.

Notations courantes

• O(1) : Complexité constante.
• O(log n) : Complexité logarithmique.
• O(n) : Complexité linéaire.
• O(n log n) : Complexité linéarithmique.
• O(n^2) : Complexité quadratique.
• O(2^n) : Complexité exponentielle.
• O(n!) : Complexité factorielle.

Complexité temporelle

• Quantifie le temps nécessaire à un algorithme pour s'exécuter en fonction de la taille de l'entrée.

Complexités temporelles courantes

• O(1) (Constant) : Le temps d'exécution est indépendant de la taille de l'entrée (ex : accès à un élément de tableau).
• O(log n) (Logarithmique) : Le temps augmente de manière logarithmique avec la taille de l'entrée (ex : recherche binaire).
• O(n) (Linéaire) : Le temps augmente linéairement avec la taille de l'entrée (ex : recherche simple).
• O(n log n) (Linéarithmique) : Plus efficace que les algorithmes quadratiques (ex : tri fusion).
• O(n^2) (Quadratique) : Le temps augmente de manière quadratique avec la taille de l'entrée (ex : tri à bulles).
• O(2^n) (Exponentielle) : Le temps double à chaque ajout à la taille de l'entrée (ex : Fibonacci récursif).
• O(n!) (Factorielle) : Le temps croît de manière factorielle avec la taille de l'entrée (ex : problème du voyageur de commerce).

Complexité spatiale

• Quantifie la quantité d'espace mémoire utilisée par un algorithme en fonction de la taille de l'entrée.
• Inclut l'espace pour les valeurs d'entrée et l'espace auxiliaire.

Complexités spatiales courantes

• O(1) : L'algorithme utilise une quantité constante d'espace (ex : utilisation de quelques variables dans une boucle).
• O(n) : L'espace utilisé augmente linéairement avec la taille de l'entrée (ex : création d'un tableau de taille n).
• O(n^2) : L'espace utilisé augmente de manière quadratique avec la taille de l'entrée (ex : création d'un tableau 2D de taille n x n).
• O(log n) : L'espace augmente de manière logarithmique avec la taille de l'entrée (ex : profondeur d'une pile de récursion, comme un arbre binaire).

Exemples

Recherche linéaire

• Recherche d'un élément dans un tableau non trié.
• Complexité temporelle : O(n).

Recherche binaire

• Recherche d'un élément dans un tableau trié.
• Complexité temporelle : O(log n).

Tri à bulles

• Un algorithme de tri simple.
• Complexité temporelle : O(n^2).

Conseils pour réduire la complexité

• Utilisation de structures de données appropriées.
• Optimisation des algorithmes (ex : diviser pour régner).
• Éviter les calculs inutiles.
• Utilisation de la mise en cache.
• Profilage du code pour identifier les goulets d'étranglement.

Conclusion

• La compréhension de la complexité algorithmique est essentielle pour écrire du code efficace.
• Le choix du bon algorithme et de la bonne structure de données peut avoir un impact significatif sur les performances.
• L'analyse et l'optimisation du code peuvent conduire à des améliorations substantielles de la complexité temporelle et spatiale.