Untitled Quiz

Analyse de la Complexité des Algorithmes

• L’analyse de la complexité d'un algorithme étudie la quantité de ressources (temps ou espace) nécessaires à son exécution.
• L'objectif est de déterminer la performance d'un algorithme en fonction de la taille des données d'entrée.
• On distingue trois cas de complexité :
  • Cas 1 : Complexité constante (O(1))
  • Cas 2 : Complexité logarithmique (O(log n))
  • Cas 3 : Complexité linéaire, polynomiale ou exponentielle (O(n), O(n²), O(2^n))

Calcul de la Complexité

• Opérations de base: Complexité est de O(1).
• Boucles: La complexité est égale à la complexité de la boucle interne multipliée par le nombre de fois que la boucle est exécutée.
• Conditions "Si/Sinon": La complexité est la valeur maximale entre la complexité de la condition "Si" et la complexité de la condition "Sinon".

Règles de Simplification

• Les constantes multiplicatives sont considérées comme égales à 1 : O(5n) = O(n).
• Les constantes additives sont considérées égales à 0 : O(n+1) = O(n).
• On conserve le terme dominant : O(n² + 2^n) = O(2^n).
• Les constantes importantes pour un calcul précis, en particulier pour des tailles d'entrée importantes.

Exemples de Complexité

• O(1): La complexité est constante, le temps d'exécution est indépendant de la taille de l'entrée.
• O(n): La complexité est linéaire, le temps d'exécution augmente proportionnellement à la taille de l'entrée.
• O(n²): La complexité est polynomiale, le temps d'exécution augmente proportionnellement au carré de la taille de l'entrée.
• O(log n): La complexité est logarithmique, le temps d'exécution augmente proportionnellement au logarithme de la taille de l'entrée.
• O(2^n): La complexité est exponentielle, le temps d'exécution augmente exponentiellement avec la taille de l'entrée.