Complexité algorithmique
1- Définition
La complexité d'un algorithme est une mesure de sa performance asymptotique dans le pire cas ; Que
signifie ‘asymptotique’ ? on s'intéresse à des données très grandes ; Que signifie ‘dans le pire cas’? On
s'intéresse à la performance de l'algorithme dans les situations où le problème prend le plus de temps.
Pourquoi? Pour être sûr que l'algorithme ne prendra jamais plus de temps que ce qu'on a estimé. Ce qui
correspond à donner une majoration du nombre d’opérations effectuées par l’algorithme.
2- La notation O
Définition
On dit que la complexité de l'algorithme est O(g(n)) ou g est une combinaison de polynômes, logarithmes
ou exponentielles. Ce qui signifie que le nombre d'opérations effectuées, noté par f(n), est borné par C*g(n),
ou C est une constante, lorsque n tend vers l'infini.
Les règles de la notation O :
• Les termes constants :
Ο Ο
• Les constantes multiplicatives sont omises :
Ο Ο Ο
• L'addition est réalisée en prenant le maximum :
Ο Ο Ο Ο Ο
• La multiplication reste inchangée :
Ο Ο Ο
Exemple : Supposant que le temps d'exécution d’un algorithme est décrit par fonction T(n) = 3n2+10n+10,
Calculer O(T(n))?
O(T(n)) = O(3 n2 + 10n + 10) = O(max (3 n2, 10n, 10)) = O(3 n2) = O (n2)
3- Classes de complexité les plus usuelles
On voit souvent apparaitre les complexités suivantes :
Classe Notation O Description Exemple
Constante O(1) Le temps d’exécution ne dépend Accéder au premier élément d'un
pas des données traitées ensemble de données
Linéaire O(n) augmentation linéaire du temps - Parcourir un ensemble de
d'exécution quand le paramètre croit données
(si le paramètre double, le temps - somme des n premiers entiers
double). naturels
Logarithmique O(log(n)) augmentation très faible du temps conversion du décimal au
1
d'exécution quand le paramètre croit. binaire.
Quasi-linéaire O(n augmentation un peu supérieure à O(n). la somme des chiffres des n
log(n)) premiers entiers naturels
Quadratique O(n2) complexité quadratique, quand le Parcourir un ensemble de
paramètre double, le temps données en utilisant deux
d'exécution est multiplie par 4. boucles imbriquées
Polynomiale O(ni) quand le paramètre double, le temps Utiliser i boucles imbriquées
d'exécution est multiplie par 2i
Exponentielle O(an) quand le paramètre double, le temps Générer tous les sous
d'exécution est élevé à la puissance 2. ensembles possibles d'un
ensemble de données
complexité O(n!) asymptotiquement équivalente à nn
factorielle
4- Calcul complexité d'un algorithme
Le coût des instructions élémentaires
On appelle opération de base, ou opération élémentaire, toute :
- Affectation ;
- Test de comparaison : ==; <;<=;>=; ! =;
- Opération de lecture (input) et écriture (print) ;
- Opération arithmétique : +;- ; *; /;%;
- Opération d'incrémentation : a=a+1,(pas 1) a=a+n (pas n) ;
- Opération de décrémentation : a=a-1,(pas 1) a=a-n (pas n) ; Le coût d'une opération élémentaire est égal
à 1.
Le coût des instructions composées
On appelle opération composée, toute instruction contenant :
- L'exécution d'une instruction conditionnelle : Si P est une instruction conditionnelle du type Si b alors
Q1 sinon Q2 finsi, le nombre d'opérations est : Coût(P) = Coût(test) + max(Coût(Q1), Coût(Q2))
- L'exécution d'une boucle : le temps d'une boucle est égal à la multiplication de nombre de répétition
par la somme du coût de chaque instruction xi du corps de la boucle ;
Coût(boucle for) =
Coût(boucle while) =
- L'appel d'une fonction : Lorsqu'une fonction ou une procédure est appelée, le coût de cette fonction ou
procédure est le nombre total d'opérations élémentaires engendrées par l'appel de cette fonction.
- Exemple 1: Que vaut le coût de ce programme P1
2
if i%2==0 :
n=i//2 else :
i=i+1
n=i//2
Coût(P1)=Coût(i%2 == 0)+ max(Coût(n = i==2),Coût(i = i + 1; n = i//2)) =1+max(1,2) =3
- Exemple 2: Que vaut le coût de ce programme P2
while i <= n :
somme=somme+i
i=i+1
- Coût(P2)=Coût(i <= n)+Coût(somme = somme + i)+Coût(i = i + 1) =n+n+n =3n
Programmation
Pour calculer la complexité d'un programme :
1. on calcule le coût des instructions qui forment le programme;
2. on simplifie le résultat grâce aux règles de simplifications suivantes:
• on remplace les constantes multiplicatives par
• on annule les constantes additives,
• on conserve le terme dominant.
Exemple 1 :
si le coût d’un programme = 3n + 6 alors la complexité = O(n)
Exemple 2 :
si le coût d’un programme = n2 + 3n alors la complexité = O(n2)
5- Des cas de complexité fréquemment utilisés:
