Complexité algorithmique
\[ O(f(n)) \]
Notation de Landau
Définition :
La complexité mesure le nombre d'opérations effectuées par un algorithme en fonction de la taille de l'entrée.
Objectif :
Comparer l'efficacité de différents algorithmes et prédire leur comportement.
Classes de complexité
| Notation | Nom | Exemple | Croissance |
|---|---|---|---|
| O(1) | Constante | Affectation | Constante |
| O(log n) | Logarithmique | Recherche dichotomique | Lente |
| O(n) | Linéaire | Recherche séquentielle | Modérée |
| O(n²) | Quadratique | Boucles imbriquées | Rapide |
| O(2ⁿ) | Exponentielle | Problèmes combinatoires | Très rapide |
Méthodes d'analyse
Compter les opérations élémentaires
Identifier les structures itératives
Comparer avec des algorithmes connus
Choisir le pire cas
Exemples d'analyse
Boucle simple (O(n)) :
Pour i allant de 1 à n Faire
Instructions // s'exécute n fois
FinPour
// Complexité : O(n)Boucles imbriquées (O(n²)) :
Pour i allant de 1 à n Faire
Pour j allant de 1 à n Faire
Instructions // s'exécute n² fois
FinPour
FinPour
// Complexité : O(n²)Calcul de somme (O(n)) :
Variables somme, i : entier
somme ← 0
Pour i allant de 1 à n Faire
somme ← somme + i
FinPour
// Complexité : O(n)Bonnes pratiques
Identifier les opérations les plus coûteuses
Simplifier les expressions complexes
Se concentrer sur le terme dominant
Considérer le pire cas possible
Erreurs fréquentes
Ne pas compter les boucles imbriquées correctement
Oublier les conditions dans les boucles
Confondre complexité temporelle et spatiale
Ne pas simplifier les constantes
