Évaluer la complexité

#Évaluer la complexitéCopier le lien

Ordres de grandeur, notation grand-O, coûts en temps et mémoire; intuition avant formalisme.

#IntroductionCopier le lien

La complexité algorithmique permet d'évaluer l'efficacité d'un algorithme en termes de temps d'exécution et d'utilisation de la mémoire, indépendamment de l'implémentation spécifique ou de la machine utilisée.

#Notation Grand-OCopier le lien

La notation Big-O (Grand-O) décrit le comportement asymptotique d'une fonction, en se concentrant sur le terme dominant lorsque la taille de l'entrée tend vers l'infini.

#Ordres de complexité courantsCopier le lien

1. O(1) - Temps constant
2. O(log n) - Logarithmique
3. O(n) - Linéaire
4. O(n log n) - Log-linéaire
5. O(n²) - Quadratique
6. O(2ⁿ) - Exponentiel

#ExemplesCopier le lien

• O(1) : Accéder à un élément d'un tableau par son index
• O(log n) : Recherche dichotomique dans un tableau trié
• O(n) : Parcourir tous les éléments d'un tableau
• O(n²) : Boucles imbriquées sur un tableau

#Complexité en temps vs complexité en espaceCopier le lien

#Complexité en tempsCopier le lien

Mesure le nombre d'opérations élémentaires effectuées par un algorithme en fonction de la taille de l'entrée.

#Complexité en espaceCopier le lien

Mesure la quantité de mémoire utilisée par un algorithme en fonction de la taille de l'entrée.

#Analyse de la complexitéCopier le lien

Pour analyser la complexité d'un algorithme, on compte le nombre d'opérations élémentaires dans le pire cas.

#Exemple: Recherche linéaireCopier le lien

Complexité : O(n) - dans le pire cas, on parcourt tout le tableau.

#Exemple: Recherche dichotomiqueCopier le lien

Complexité : O(log n) - on divise l'espace de recherche par deux à chaque itération.