Chapitre I :
Complexité des algorithmes
Pourquoi la complexité?
Sol 1
Sol 2
Sol 3 Comparaison Meilleur sol
Un problème et choix
...
...
Sol N
Meilleur sol est l’algorithme le plus efficace.
L’efficacité= MOINS de temps d'exécution, moins de place
mémoire.
Objectif
Estimer le «Temps d’exécution» pour comparer plusieurs
algorithmes pour le même problème.
Mesure de la complexité en temps
Définition : Une opération OP est fondamentale pour un
algorithme A si le nombre de OP influe directement sur le
temps d’exécution de l’algorithme A.
Exemples d’opérations fondamentales
Algorithme Opérations fondamentales
Recherche d’un élément dans comparaison entre l’élément cherché et les
une liste en mémoire centrale composants de la liste
Trier une liste d’éléments - comparaison entre deux éléments
- déplacement des éléments
multiplier deux matrices de - multiplication
nombres - addition
Complexité d'une séquence d'instructions
S = Begin
i1 ; i2 ; . . . ; in
End
n
Donc Nb( S ) Nb(i p )
p 1
Nb (ik) = le nombre d'opérations fondamentales dénotées Opf contenues
dans l'instruction algorithmique ik.
Complexité d'une instruction conditionnelle
Cond = if Expr then E1 else E2 ;
Donc Nb( Cond ) Nb( Expr) +Max ( Nb( E1 ) , Nb( E2 ) )
Complexité d'une itération finie bornée
Iter = Itération Expr(i)
S
finItér
Donc : Nb( Iter ) = [ Nb( S) + Nb (Expr(i)) ] x Nb_itérations
Par exemple dans le cas d'une boucle For :
Iter = For I := a to b do
Begin
i1 ; i2 ; . . . ; in
End;
Complexité de la
Donc : condition de
continuité
n
Nb( Iter ) b a 1 Nb(i p ) 1
I<=b
p 1
Complexité des appels de sous-programmes :
Sous-pgme A
Sans récursivité : I1;
I2;
Nb(A)=Nb(I1)+Nb(I2)+Nb(B)+Nb(I3) Appel de B;
I3;
En cas de récursivité, calculer Nb(A) donne lieu à la résolution d'une relation
de récurrence.
Exemple:
Function fact(n : integer) : integer;
Begin
If n=0 then fact:=1 else fact:=n*fact(n-1);
End;
Le nombre T(n) d’opérations fondamentales (*) vérifie :
T(0)=0 et T(n)=T(n-1)+1; pour n≥1
Par une résolution directe on obtient : T(n)=n.
Exemple d'indication :
Soit l’algorithme de recherche séquentielle d’un élément X dans une liste L.
int Chercher (Element L[n] , Element X)
{
(1) int j=0;
(2) while (j<n and L[j]!=X) j++;
(3) if (j>=n) j=-1;
return j;
}
La complexité de cet algorithme=Fonction (nombre d'itérations, nombre
d'opérations par itération).
3 opérations fondamentales dans la ligne (2) : j<n, L[j]!=X et j++
Les 2 opérations : j<n et j++ dépendent de la programmation.
Opération fondamentale à retenir = comparaison (L[j]!=x ) dans la ligne (2).
j=0
Non j<n et Oui
L[j]≠X
j++
Non Oui
j>=n
j=-1
Complexité=j+1
j[0 . . n-1]
Complexité =n
End
Conclusion :
La complexité (nbre de comparaisons L[j]≠x) dépend de la taille
des données.
Complexité au pire = n
Complexité au meilleur = 1
Complexité moyenne comprise entre 3 et 3n
Pour une taille fixée, elle dépend des différentes données possibles.
Complexité en moyenne et au pire :
Soit coûtA(d) =complexité de l’algo A pour la donné d.
L'ensemble des données de taille n est noté Dn.
La complexité dans le meilleur des cas
MinA(n) = min {coûtA(d) ; dDn}
La complexité dans le pire des cas
MaxA(n) = max {coûtA(d) ; dDn}
La complexité moyenne
Moy A (n) P(d ) cout
dDn
A (d )
où P(d) est la probabilité d'avoir la donnée d en entrée de l'algorithme
Remarque:
MinA(n) ≤ MoyA (n) ≤MaxA(n)
Exercices du TD N° 01
Exercice 01: Soient les matrices réelles n x n : A=(aij), B=(bij) et C=(cij).
Etudier la complexité de l’algo suivant qui calcule les coefficients (cij) de la
matrice produit C= A x B selon la formule classique :
n
cij aik .bkj pour i, j compris entre 1 et n
k 1
Const int n=8;
typedef float matrice[n][n];
void multimat(matrice a, matrice b, matrice c)
{for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
{ c[i][j]=0;
for (int k=0; k<n; k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
}
Exercice 02: Soit l’algo qui calcule la valeur du
polynôme : 𝑃(𝑥, 𝑛) = 𝑛𝑖=0 𝑎𝑖 𝑥 𝑖 , en un point donné x.
On dispose de 3 versions de cet algo.
a) p=a[0];
for (i=1; i<=n;i++){ xpi=puissance(x, i);
p=p+a[i]*xpi;}
b) p=a[0]; xpi=1;
for (i=1; i<=n;i++){ xpi=xpi*x;
p=p+a[i]*xpi;}
b) Méthode de Horner
p=a[n];
for (i=n-1; i>=0;i--){ p=p*x+a[i];
Calculer la complexité de chaque version.
Exercice 03: Calculer la complexité des 2 algos
suivants pour la suite de Fibonnacci.
a) int Fib (int n)
{ int tab[n+1];
tab[0]=1; tab[1]=1;
for (int i=2; i<=n; i++) tab[i]=tab[i-1]+tab[i-2];
return tab[n];}
b) int Fib (int n)
{ int tab[2];
tab[0]=1; tab[1]=1;
for (int i=1; i<=n/2; i++) {tab[0]=tab[0]+tab[1];
tab[1]=tab[0]+tab[1];
if (pair(n)) return tab[0]; else return tab[1];}
Exercice 04: Travail Personnel
On considère un tableau à une dimension TEXT[]
contenant des lettres majuscules. On désire compter la
fréquence des 26 lettres de l’alphabet. Ecrire deux
fonctions qui donnent en sortie un tableau de
fréquences. Dans la première fonction, le tableau est
parcouru 26 fois, la deuxième fait le calcul en un seul
parcours. On suppose qu’on a une fonction auxiliaire
Position(lettre) qui donne la position de chaque lettre
dans l’alphabet. Pos(‘A’)=1; . . . Pos(‘Z’)=26.
