La complexité des algorithmes
Calcul de la complexité asymptotique
L'efficacité d'un algorithme est jugée par l'évaluation de son temps d'exécution et par les ressources matérielles mises à sa disposition au moment de l'exécution. Cependant, pour évaluer l'efficacité d'un algorithme on s'intéresse surtout à calculer son temps d'exécution. Mais vu que ce temps peut changer d'une machine à une autre (une machine plus performante exécutera l'algorithme plus rapidement), alors on s'intéresse surtout à évaluer l'ordre de grandeur du nombre d'opérations exécutées dans un algorithme. On parle alors de complexité asymptotique.La complexité asymptotique est représentée par le symbole Grand O. On peut donc avoir une complexité constante qui vaut O(1), une complexité linéaire qui vaut O(n), une complexité quadratique qui vaut O(n²), une complexité logarithmique qui vaut O(log(n)) etc...
Complexité d'un algorithme
La complexité d'un algorithme est une mesure de la ressource requise pour exécuter cet algorithme. Cela peut être mesuré en termes de temps d'exécution (nombre d'opérations) ou d'espace mémoire utilisé.
La complexité d'un algorithme est importante car elle permet de prédire ses performances et de comparer différentes solutions algorithmiques.
Il existe différents types de complexité, mais les deux principaux sont la complexité temporelle (notée O) et la complexité spatiale (notée S).
La complexité temporelle d'un algorithme mesure le temps d'exécution en fonction de la taille de l'entrée. Par exemple, si un algorithme prend quadratiquement plus de temps à mesure que la taille de l'entrée double, sa complexité temporelle est O(n²).
La complexité spatiale d'un algorithme mesure la quantité de mémoire utilisée en fonction de la taille de l'entrée. Par exemple, si un algorithme utilise linéairement plus d'espace mémoire à mesure que la taille de l'entrée double, sa complexité spatiale est S(n).
Calcul de la complexité
Voici deux exemples de calcul résolus en pseudo-code et l'analyse de leur complexité :
Exemple 1 : Calcul de la somme des éléments d'un tableau
```
fonction somme_tableau(tableau)
somme = 0
pour chaque élément dans tableau
somme = somme + élément
fin pour
renvoyer somme
fin fonction
```
Dans cet exemple, le nombre d'opérations effectuées dépend de la taille du tableau "tableau". Donc, la complexité temporelle est linéaire et notée O(n), où n est la taille du tableau.
La complexité spatiale est constante, car l'algorithme utilise une quantité fixe de mémoire pour stocker la somme et les variables temporaires, indépendamment de la taille du tableau. Donc, la complexité spatiale est S(1).
Exemple 2 : Recherche d'un élément dans une liste
```
fonction recherche_liste(liste, valeur)
pour chaque élément dans liste
si élément = valeur alors
renvoyer Vrai
fin si
fin pour
renvoyer Faux
fin fonction
```
Dans cet exemple, le nombre d'opérations dépend du nombre d'éléments dans la liste. Donc, la complexité temporelle est linéaire et notée O(n), où n est le nombre d'éléments dans la liste.
La complexité spatiale est constante, car l'algorithme n'utilise qu'un espace mémoire fixe pour stocker les variables temporaires, indépendamment de la taille de la liste. Donc, la complexité spatiale est S(1).
Calculer la complexité de l’algorithme ci-dessous :
Début
K <- 0
I <-1
Tant que I <= N faire
R <-R+T(I)
Si R > 1000 Alors
R <- 2*R
Fin Si
I <- I+1
Fin
Résolution
Pour calculer la complexité de cet algorithme, nous pouvons utiliser les formules suivantes :
- Le nombre total d'itérations effectuées dans la boucle "Tant que" est le nombre N lui-même, puisque I est incrémenté de 1 à chaque itération jusqu'à ce qu'il atteigne N.
- La complexité des opérations à l'intérieur de la boucle (addition, vérification et multiplication) est généralement considérée comme constante, c'est-à-dire O(1), car elle ne dépend pas de la taille de N.
Par conséquent, la complexité totale de cet algorithme peut être exprimée comme : O(N * 1), ce qui se simplifie en O(N). Cela signifie que la complexité de l'algorithme est linéaire, car elle croît linéairement avec la taille de N.
En résumé, pour analyser la complexité d'un algorithme en pseudo-code, vous devez déterminer combien d'opérations ou de mémoire il utilise en fonction de la taille de l'entrée.