13/03/2014
Notion de complexité d'un algorithme
Faculté des Sciences Tétouan
Département d’Informatique Pour évaluer l’efficacité
efficacité d'un algorithme, on calcule sa complexité
Mesurer la complexité revient à quantifier le temps d'exécution et l'espace
mémoire nécessaire
Le temps d'exécution est proportionnel au nombre des opérations
Complexité d'un algorithme effectuées. Pour mesurer la complexité en temps, on met en évidence
certaines opérations fondamentales, puis on les compte
Le nombre d'opérations dépend généralement du nombre de données à
traiter. Ainsi, la complexité est une fonction de la taille des données. On
s'intéresse souvent à son ordre de grandeur asymptotique
Said EL GAROUANI
En général, on s'intéresse à la complexité dans le pire des cas et à la
complexité moyenne
1 2
Structures de données Structures de données
avancées : les tableaux avancées : les tableaux
• Organisation contiguë des données : les • Remarque : les données doivent être du
éléments sont placés l’un à côté de l’autre. même type.
• Syntaxe :
var tab : tableau[indices] de éléments; • Pour accéder au k ième élément du tableau
où indices est l’ensemble des indices tab, on note tab[k].
• Exemple :
var tab :tableau[0..9] de entiers;
3 4
Algorithmes sur les Algorithmes sur les
tableaux tableaux
• Recherche d’un élément : deux types de • Recherche d’un élément :
recherche : Algorithme rechercher(x,tab,nbr)
var x : élément;
i,nbr : entier ;
Question 1 : est-ce que l’élément figure dans le trouvé : booléen;
tab : tableau[1…TailleMax] de élément;
tableau ? debut
trouvé faux;
pour i = 1 à nbr faire
Question 2 : si oui quel est son indice dans le si tab[i] = x alors trouvé vrai;
tableau ? fin pour
retourner trouvé;
fin
5 6
1
13/03/2014
Algorithmes sur les Recherche séquentielle : complexité
tableaux Pour évaluer l’efficacité de l'algorithme de recherche séquentielle, on va
calculer sa complexité dans le pire des cas. Pour cela on va compter le
nombre de tests effectués
• Recherche de l’indice d’un élément dans un tableau :
Le pire des cas pour cet algorithme correspond au cas où x n'est pas dans
Algorithme rechercher_indice(x,tab,nbr) le tableau T
var x : élément;
i,indice,nbr : entier ; Si x n’est pas dans le tableau, on effectue 3N tests : on répète N fois les
tab : tableau[1…TailleMax] de élément; tests (i < N), (Trouvé=Faux) et (T[i]=x)
debut
indice -1; La complexité dans le pire des cas est d'ordre N,N (on note O(N))
O(N)
pour i = 1 à nbr faire
si tab[i] = x alors indice i; Pour un ordinateur qui effectue 106 tests par seconde on a :
fin pour
retourner indice; N 103 106 109
fin
7 Temps 1ms 1s 16mn40s 8
Algorithmes sur les Algorithmes sur les
tableaux tableaux
• Recherche d’un élément dans un tableau trié :
• Recherche d’un élément dans un tableau trié :
recherche « naïve » :
recherche dichotomique
principe : parcourir le tableau jusqu’à trouver Principe :
l’élément recherché. i) On compare l ’élément à l ’élément du milieu du
Critique de la méthode : on n’exploite pas le fait tableau.
que le tableau est trié.
Première solution : s’arrêter dès que l’on ii) Si égales ⇒ arrêt.
rencontre un élément plus grand que l’élément
recherché.
Deuxième solution : faire une recherche iii) Sinon, on effectue la recherche à la moitié du
dichotomique. tableau.
9 10
Algorithmes sur les
Exemple d'exécution
tableaux Considérons le tableau T :
• Recherche dichotomique : 4 6 10 15 17 18 24 27 30
Algorithme recherche_dicho(x,nbr,tab)
var x : élément; Si la valeur cherché est 20 alors les indices g, d
nbr : entier; et m vont évoluer comme suit : g 0 5 5 6
tab : tableau[1…TailleMax] de élément;
trouvé : booléen;
début
d nbr; g 0; trouvé faux; d 8 8 5 5
tant que g <= d faire Si la valeur cherché est 10 alors les indices g, d
m (d+g)/2; et m vont évoluer comme suit :
si tab[m] = x alors trouvé vrai; m 4 6 5
sinon si tab[m] > x alors d m-1;
sinon g m+1; g 0 0 2
fin si;
fin si;
fin tant que;
retourner trouvé; d 8 3 3
fin;
11 m 4 1 2 12
2
13/03/2014
Algorithmes sur les
Recherche dichotomique : complexité
tableaux
La complexité dans le pire des cas est d'ordre log 2 N
• Insertion d’un élément dans un tableau : deux
L'écart de performances entre la recherche séquentielle et la cas de figure :
recherche dichotomique est considérable pour les grandes
valeurs de N
Le tableau n’est pas trié : on insère à la fin
− Exemple: au lieu de N=1milion ≈220 opérations à ou bien à un endroit spécifié.
effectuer avec une recherche séquentielle il suffit de 20
opérations avec une recherche dichotomique
Le tableau est trié l’élément doit être
inséré au bon endroit.
13 14
Algorithmes sur les Algorithmes sur les
tableaux tableaux
• Insertion d’un élément à une position k dans • Insertion d’un élément à une position k dans un
un tableau : tableau :
Algorithme inserer_position(x,pos,nbr,tab)
var x : élément;
Principe : pos,i,nbr : entier;
tab : tableau[1…TailleMax] de élément;
début
i) On décale d’un cran tous les éléments du tableau pour i = nbr+1 à pos+1 par pas de –1 faire
à partir de la position k+1 vers la droite. tab[i] tab[i-1];
fin pour;
ii) On insère l’élément à sa place. tab[pos] x;
nbr nbr+1;
15
fin; 16
Algorithmes sur les Algorithmes sur les
tableaux tableaux
• Insertion d’un élément dans un tableau trié
Algorithme inserer_trie(x,nbr,tab)
var x : élément;
• Insertion d’un élément dans un tableau trié pos,i,nbr : entier;
tab : tableau[1…TailleMax] de élément;
Principe : début
pos 1;
tant que tab[pos] < x et pos < nbr faire
i) On cherche la position k où l’on doit insérer pos pos+1;
l’élément. fin tant que;
si pos = nbr alors tab[nbr+1] x;
sinon
ii) On décale d’un cran tous les éléments du tableau à pour i = nbr+1 à pos+1 par pas de –1 faire
partir de la position k+1 vers la droite. tab[i] tab[i-1];
fin pour;
tab[pos] x;
iii) On insère l’élément à sa place. fin si;
nbr nbr+1;
fin;
17 18
3
13/03/2014
Récursivité
Récursivité
Raisonnement par récurrence
hypothèse de récurrence
• Exemple : Montrer que : n
n( n + 1)
S (n) = ∑ i =
Preuve : i =0 2 n +1 n
Cas de base : S ( n + 1) = ∑ i = ( ∑ i ) + ( n + 1) = S ( n ) + ( n + 1)
i=0 i=0
0
0 ( 0 + 1)
– n=0: S (0 ) = ∑i=0= = 0 (Vrai)
i=0 2
1
1 (1 + 1 )
– n=1: S (1 ) = ∑ i = 0 +1= =1 (Vrai)
i= 0 2 n ( n + 1)
= + ( n + 1)
Récurrence : 2
n ( n + 1)( n + 2 )
Hypothèse : S(n) est vrai, = ( n + 1)( + 1) = (Vrai )
2 2
montrer que S(n+1) est vrai
19 20
Récursivité Récursivité
Équations de récurrences • Action récursive
• Base : S(0) = 0 « une action A est exprimée de façon récursive si la
• Récurrence : S(n+1) = S(n)+(n+1) décomposition de A fait appel à A. »
• Action calculer S(n) :
La récursivité est un
Appliquer les deux règles suivantes:
mécanisme de calcul puissant!!
1) S(0) = 0
Résoudre un problème de taille n 2) S(n) = S(n-1) + n , n>0
peut se ramener d’un (plusieurs) sous S(3) ?
problèmes de taille plus réduite ... = S(2) +3 = (S(1)+2 ) +3
= ((S(0)+1)+2)+3 = ((0+1)+2)+3 = 6
21 22
Récursivité
• Objet récursif Récursivité
• Exemple (suite)
« La définition d ’un objet est récursive lorsqu’elle se
D’après la définition précédente :
formule en utilisant l’objet même qu’elle entend définir »
«a» est une chaîne :
• Exemple (déf. récursive d’une chaîne) un caractère ‘a’ suivi d’une chaîne vide
«ab» est une chaîne :
Une chaîne de caractère est : un caractère ‘a’ suivi de la chaîne « b »
– soit la chaîne vide La récursivité est un
– soit un caractère suivi d’une chaîne de caractère mécanisme puissant de définition d’objets!
23 24
4
13/03/2014
Récursivité Vs Itération Récursivité : applications
• Exemple 1 : calcul de la factorielle
Itération Récursivité Équations de récurrences :
procédure Itération( ) procédure Itération( ) – 0! = 1 (base)
Tantque (condition) faire Si (condition) alors – n! = n(n-1)! (récurrence)
<Instructions> <Instructions>
S(n-1) Itération() fonction fact(d n:entier): entier
fin tantque début
fin si
fonction S(n) : entier fonction S(n) : entier si n = 0
S :=0 Si (n=0) alors fact:= 1
Tant que (n>0) faire alors S:= 0 sinon fact:= n * fact(n-1)
S:=S+n sinon S:= +n fin si
n:=n-1 fin si fin
fin tant que
retourner S Que se passe t-il si n <0? récursivité infinie
25 26
Récursivité : applications Récursivité : applications
• Exemple 2 : suite de fibonacci • Exemple 2 (suite)
Équations de récurrences : Voyons l’exécution : u(9)?
– u(0) = 0, u(1) = 1 (Base) u(9)
u(8) u(7)
– u(n) = u(n-1)+u(n-2), n>1 (récurrence)
u(7) u(6) u(6) u(5)
fonction u(d n:entier) : entier
… … … …
si (n=0) ou (n=1)
alors u:= n ≈ O(2n-1) appels à la fonction u
sinon u:= u(n-1) + u(n-2) pour n = 100 , O(299) ≈ O(1033) !!!
Une solution récursive n’est pas toujours viable
fin si
...
27 28
fin action
Récursivité : applications Récursivité : applications
Les Tours de Hanoï (TH)
Exemple 2 (suite) : solution itérative
fonction u(d n:entier) : entier • 3 axes, n disques concentriques
début
var x, y, z, i : entier
si (n=0) ou (n=1) alors retourner n
sinon x:=0 {u(0)}
y:=1 {u(1)} n
pour i allant de 2 à n faire
z:= x+y {u(n) = u(n-1)+u(n-2)} G(auche) M(ilieu) D(roite)
x:=y
y:=z • But : déplacer tous les disques de G à D
fin pour • Règles :
retourner z – 1 seul disque peut être déplacé à la fois
fin si – 1 disque ne peut jamais être déposé sur un plus petit
29 30
fin – 1 disque ne peut être déposé que sur G, M ou D
5
13/03/2014
Récursivité : applications Récursivité : applications
TH : idée de la solution récursive
1 3
• exprimer le problème des n disques à l ’aide de la
même solution sur n-1 disques
2
• (base) savoir résoudre le problème pour 1 disque
G(auche) M(ilieu) D(roite)
Équations de récurrences (k=2)
(k=3) …, bonne chance
Récurrence :
Hypothèse: on connaît la solution de problème pour k disques
G(auche) M(ilieu) D(roite)
Trouver la solution pour k+1 disques
(k=1) 31 32
Récursivité: applications Récursivité: applications
algorithme hanoi(
hanoi(inout,output
inout,output);
);
var n :entier; { nombre de disques}
k procédure deplacer(n
deplacer(n : entier, G :char, M:char, D:char)
1(hypo) 3(hypo) debut
k+1
si (n=1)alors debutsi
ecrire("déplacer
ecrire("déplacer un disque de ") ;
G(auche) M(ilieu) 2 D(roite) ecrire(G,
ecrire(G, " vers ", D);
Solution finsi sinon debut
procédure déplacer(n, G, M, D) déplacer(n--1, G, D, M);
déplacer(n
« déplacer un disque de G vers D en utilisant l’axe M » ecrire("déplacer
ecrire("déplacer un disque de ") ;
(Base) n=1, déplacer un disque de G vers D ecrire(G,
ecrire(G, " vers ", D);
déplacer(n--1, M, G, D);
déplacer(n
(récurrence)
fin;
• déplacer(n
déplacer(n--1, G, D, M) debut
ecrire("Nb
ecrire("Nb disques? " ) ; lire(n);
• déplacer un disque de G vers D deplacer(n,
deplacer (n, ‘g’, ‘m’, ‘d’);
fin.
• déplacer(n
déplacer(n--1, M, G, D) 33 34
Récursivité
Conclusion
• La récursivité est un principe puissant nous
permettant de :
– définir des structures de données complexes
– de simplifier les algorithmes opérants sur ces
structures de données
35
