Peu importe la filière, tu auras des épreuves d’informatique aux concours. De nombreuses questions portent sur l’analyse de la complexité d’un algorithme. Voici quelques conseils pour t’aider à la calculer.
Qu’est-ce que la complexité d’un algorithme ?
La complexité d’un algorithme est un concept qui permet de comparer l’efficacité des algorithmes en identifiant celui qui offre la meilleure performance. Il existe deux types de complexité :
- complexité temporelle : elle mesure la rapidité d’exécution d’un algorithme ;
- complexité spatiale : elle évalue la mémoire supplémentaire utilisée, en plus des données d’entrée.
Ces deux types de complexité sont indépendants. Un algorithme peut avoir une excellente complexité temporelle tout en affichant une mauvaise complexité spatiale, et inversement.
Dans le cadre du programme de CPGE, l’accent est mis sur la complexité temporelle, que nous allons développer ici.
La notation grand O
Définition : On note \( u _{ n } = O \left( v _{ n } \right) \), quand il existe \( n _{ 0 } \in \mathbb{N} \) et un réel \( k>0 \) tel que :
\[ \forall n \geq n _{ 0 } , \, \left| u _{ n } \right| \leq k \left| v _{ n } \right| \]
On exprimera la complexité sous la forme \( O \left( f \left( n \right) \right) \). Cela permet de déterminer la complexité en fonction de la taille de l’entrée \(n\).
Remarque : si la complexité exacte d’un algorithme est \( O \left( 3n ^{ 3 } +4n ^2 +n+3 \right) \), on peut simplifier cela en \( O \left( n ^{ 3 } \right) \)
Comparaison des performances des algorithmes
Voici un tableau présentant les complexités temporelles classées par ordre croissant.
|
\( O \) |
Complexité |
|
\( O(1) \) |
Constant |
|
\( O(log\,n)\) |
Logarithmique |
|
\( O(n) \) |
Linéaire |
|
\( O(n\,log\,n) \) |
Quasi linéaire |
|
\( O(n^2) \) |
Quadratique |
|
\( O(n^p) \), avec \(p \geq 2\) |
Polynomial |
| \( O(a^n) \), avec \(a >1\) |
Exponentiel |
Calculer la complexité temporelle d’un algorithme : meilleur et pire cas
La complexité temporelle est déterminée en comptant le nombre total d’opérations fondamentales (telles que les opérations arithmétiques, les comparaisons, les accès aux données et les affectations) réalisées par l’algorithme.
Exemple : Recherche d’un élément dans une liste non triée
Notons \(n=len(liste)\), qui représente la taille de l’entrée.
- La boucle se déroule \(n\) fois.
- L’instruction if, l’accès à liste[i] et le test d’égalité se déroulent en temps constant (3 opérations)
- Le return compte pour une opération élémentaire.
La vérification se réalise au maximum \(3n+1\) fois. Or, \( 3n+1 \leq 4n \) donc la complexité temporelle dans le pire des cas est \( O \left( n \right) \).
Dans le meilleur des cas, c’est-à-dire liste[0]==element : la boucle s’arrête après un passage, ce qui donne une complexité dans le meilleur des cas de : \( O \left( 1 \right) \).
Par défaut, on déterminera toujours la complexité dans le pire des cas.
Calculer la complexité d’un algorithme : quadratique, exponentielle et logarithmique
Algorithme en complexité quadratique
Algorithme de vérification de doublons :
On se place dans le pire des cas, c’est-à-dire qu’il n’y a aucun doublon dans la liste.
Décomposons le nombre de comparaisons effectuées pour chaque valeur de \(i\) :
- Lorsque \(i = 0\), la boucle \(j\) va de \(1\) à \(n-1\), ce qui donne \(n-1\) comparaisons.
- Lorsque \(i = 1\), la boucle \(j\) va de \(2\) à \(n-1\), ce qui donne \(n-2\) comparaisons.
- Lorsque \(i = 2\), la boucle \(j\) va de \(3\) à \(n-1\), ce qui donne \(n-3\) comparaisons.
- …
Ainsi le nombre total de comparaisons est \( \left( n-1 \right) + \left( n-2 \right) + \left( n-3 \right) + \cdots +1= \displaystyle \frac { n \left( n-1 \right) } { 2 } \).
Conclusion : la complexité est \( O \left( n ^2 \right) \).
Algorithme en complexité exponentielle
Algorithme pour calculer les termes de la suite de Fibonacci :
Notons \(T(n)\) le nombre total d’opérations nécessaires pour calculer le n-ième nombre de Fibonacci.
On a la relation de récurrence suivante : \(T(n)=T(n-1)+T(n-2)+1\)
Remarque : le \(+1\) correspond à l’addition entre fibonacci(n-1) et fibonacci(n-2).
Dès lors, \( u _{ n } =T(n)-1=T(n-1)+T(n-2)\). On peut ainsi trouver une expression explicite de \( u _{ n }\).
Lire : Suite de Fibonacci : définition, formules et propriétés
Ce qui nous donne \( u _{ n } = \displaystyle \frac { \varphi ^{ n } – \left( 1- \varphi \right) ^{ n } } { \sqrt{ 5 } } \) avec \(\varphi = \displaystyle \frac { 1+ \sqrt{ 5 } } { 2 } \)
On peut donc en déduire une expression de \( T(n)\) : \( T(n) =\displaystyle \frac { \varphi ^{ n } – \left( 1- \varphi \right) ^{ n } } { \sqrt{ 5 } } +1 \)
Finalement : \( T \left( n \right) = O \left( \varphi ^{ n } \right) \).
Conclusion : la complexité de cet algorithme est \(O \left( \varphi ^{ n } \right) \).
Algorithme en complexité logarithmique
Algorithme de recherche de la position d’un élément dans une liste triée :
On commence par noter \(len(liste)=n\).
La taille de l’instance \(n\) (la taille de la liste sur laquelle l’algorithme opère à un moment donné) est divisé par 2 à chaque itération de la boucle, la taille finale de l’instance est \( \left\lfloor \displaystyle \frac { n } { 2 ^{ k } } \right\rfloor \), avec \(k\) le nombre d’itérations.
Comme la plus petite taille possible d’une instance est de \(1\), on a \( 1 \leq \frac { n } { 2 ^{ k } } \). Après calcul, on obtient \(k \leq \displaystyle \frac { log(n) } { log(2)} \)
Conclusion : la complexité de cet algorithme est \(O \left( \log n \right) \)
Lire : Tout comprendre sur la méthode de dichotomie en Python
