COMPLEXITE DES ALGORITHMES
MSI 1 U-FOAD
Klazé Faïrousse DAO
[email protected] ALGORITHMES
P: est un problème
M: est une méthode pour résoudre le problème P
Algorithme: une description de la méthode M dans un langage
algorithmique
Du nom du Mathématicien Perse Al Khuwarizmi
MSI 1 U-FOAD 2
STRUCTURES
ALGORITHMIQUES
Structures de contrôle :
Séquence
Embranchement (ou sélection)
Boucle (ou itération)
Structures de données :
Constantes
Variables
Tableaux
Structures récursives (Listes, arbres, graphes)
MSI 1 U-FOAD 3
COMPLEXITE DES
ALGORITHMES
On veut:
Evaluer l’efficacité de la méthode M
Comparer M avec une autre méthode M’, indépendamment de
l’environnement (machine, système, compilateur,…)
MSI 1 U-FOAD 4
COMPLEXITE DES
ALGORITHMES
Evaluation du nombre d’opérations élémentaires en fonction :
De la taille des données
De la nature des données
Notations :
n: taille des données
T(n) : nombre d’opérations élémentaires
Configurations caractéristiques:
Meilleur cas
Pire des cas
Cas moyen
MSI 1 U-FOAD 5
EVALUATION T(n)
(SEQUENCE)
Somme des coûts:
Traitement 1 T1(n)
T(n) = T1(n) + T2(n)
Traitement 2 T2(n)
MSI 1 U-FOAD 6
EVALUATION T(n)
(EMBRANCHEMENT)
Max des coûts:
Si <condition> alors
Traitement 1 T1(n)
max(T1(n) ,T2(n))
Sinon
Traitement 2 T2(n)
MSI 1 U-FOAD 7
EVALUATION T(n)
(BOUCLE)
Somme des coûts des passages successifs:
Tant que <condition> faire 𝑘
Traitement 1 T1(n) ∑ 𝑇 𝑖(𝑛)
𝑖 =1
fin faire
Ti(n) : coût de la ième itération souvent défini par une équation
récursive
MSI 1 U-FOAD 8
EVALUATION T(n)
(FONCTIONS
RECURSIVES)
fonction FunctionRecursive (n)
1 si (n>1) alors
2 FunctionRecursive (n/2), coût T(n/2)
3 Traitement(n), coût C(n)
4 FunctionRecursive (n/2), coût T(n/2)
Equation récursive: T(n)=2*T(n/2)+C(n)
Si C(n)=1 alors T(n)=K*n
Si C(n)=n alors T(n)=K*n*log n
MSI 1 U-FOAD 9
NOTION DE LANDAU
O(f(n))
c x f(n)
T(n) = O(f(n))
n0 n
Caractérise le comportement asymptotique (i.e quand n
T(n)=O(f(n)) si tels que >no, T(n)
MSI 1 U-FOAD 10
NOTATION
C2*f(n)
T(n)
C1*f(n)
n0 n
T(n)= (f(n)) si tels que >no,
MSI 1 U-FOAD 11
EXEMPLES
f(n)=n3+2n2+4n+2=O(n3) (si n)
f(n)=n log n+12n+888 = O(n log n)
f(n)=1000n10-n7+12n4+ = O(2n)
MSI 1 U-FOAD 12
PRINCIPALES
CLASSES DE
COMPLEXITE
0(1) temps constant
O(log n) logarithmique
0(n) linéaire
O(n*log n) tris(par échanges)
O(n2) quadratique, polynomial
O(2n) exponentiel (problèmes très difficiles)
MSI 1 U-FOAD 13
Exemple: Permutation
fonction permutation( S, i, j)
1 tmp := S[i], coût c1
2 S[i] := S[j], coût c2
3 S[j] := tmp, coût c3
4 Renvoyer S coût c4
Coût total : T(n) = c1+c2+c3+c4 = O(1)
MSI 1 U-FOAD 14
Exemple: recherche
séquentielle
fonction permutation( S, i, j)
1 tmp := S[i], coût c1
2 S[i] := S[j], coût c2
3 S[j] := tmp, coût c3
4 Renvoyer S coût c4
Coût total : T(n) = c1+c2+c3+c4 = O(1)
MSI 1 U-FOAD 15
Exemple: tri à bulle
fonction Tri( S, n)
1 pour i := n à 2 faire (n-1 fois)
2 pour j := 1 à i-1 faire (n-1 fois)
3 Si (S[j]>S[j+1] alors
4 Permuter S[j] et S[j+1] dans S
T(n) = Cperm+=)
MSI 1 U-FOAD 16
EQUATION
RECURSIVE
Boucles itératives, fonctions récursives (approches de type diviser
pour régner notamment)
Cas général: T(n)= a * T(n/b)+ f(n)
Méthode par substitution,
Méthode par développement itératif,
Méthode générale.
MSI 1 U-FOAD 17
Par Substitution
Principe: On vérifie une intuition
T(n)= a * + et T(1)
Hypothèse: T(n)=g(n) (intuition)
Conclusion: a*g(n/b) +f(n) = g(n) et g(1)=c à démontrer en fixant
les constantes
MSI 1 U-FOAD 18
Par Substitution
Fonction RechercheDichotomique (x, <S1,…,Sn>)
1 g :=0, d := n+1,
2 tant que faire stoppe quand
3 si alors
4 g := (g+d)/2, et donc
5 Sinon
6 d := (g+d)/2 et donc
7 Renvoyer d, et donc
Nombre d’itérations T(n) = 1+T(n/2)
MSI 1 U-FOAD 19
Par Substitution:
Equations récursives
T(n) = 1+T(n/2) et T(1)= 1*
Intuition : T(n)=O(log2 n)
Hypothèse: T(n)= a * log2n + c donc
T(n/2)=a*log2n - a+c en substituant on a:
T(n)=1 + a*log2n – a+c donc 1 - a+c =c et a=1, et puisque
T(1)=1 donc c=1
Conclusion: T(n)=log2n+1
*s’il ya un élément on fera une itération
MSI 1 U-FOAD 20
Méthode itérative: Rappel
sommations
MSI 1 U-FOAD 21
Méthode itérative:
Equations récursives
fonction TriParFusion (S,n)
1 si(n
2 renvoyer S
3 décomposer S en S1 et S2 , (n)
4 S1:=TriParFusion(S1), (T([n/2]))
5 S2:=TriParFusion(S2), (T([n/2]))
6 S:= fusion(S1,S2), (n)
7 renvoyer S
T(n) = 1+n+2*T(n/2)+n et T(1)=1
MSI 1 U-FOAD 22
Méthode itérative:
Equations récursives
T(1)=1
T(n) = 2n+1+2T(n/2)
MSI 1 U-FOAD 23
Méthode itérative:
Equations récursives
T(1)=1
T(n) = 2n+1+2T(n/2)
donc T(n/2)=n+1+2T(n/4)
T(n)=(2n+1)+(2n+2)+4T(n/4)
MSI 1 U-FOAD 24
Méthode itérative:
Equations récursives
T(1)=1
T(n) = 2n+1+2T(n/2)
donc T(n/2)=n+1+2T(n/4)
T(n)=(2n+1)+(2n+2)+4T(n/4)
or T(n/4)=n/2+1+2T(n/8)
T(n)=(2n+1)+(2n+2)+(2n+4)+8T(n/8)
MSI 1 U-FOAD 25
Méthode itérative:
Equations récursives
T(1)=1
T(n) = 2n+1+2T(n/2)
donc T(n/2)=n+1+2T(n/4)
T(n)=(2n+1)+(2n+2)+4T(n/4)
or T(n/4)=n/2+1+2T(n/8)
T(n)=(2n+1)+(2n+2)+(2n+4)+8T(n/8)
…
T(n)=
MSI 1 U-FOAD 26
Méthode itérative:
T(1)=1 Equations récursives
T(n) = 2n+1+2T(n/2)
donc T(n/2)=n+1+2T(n/4)
T(n)=(2n+1)+(2n+2)+4T(n/4)
or T(n/4)=n/2+1+2T(n/8)
T(n)=(2n+1)+(2n+2)+(2n+4)+8T(n/8)
…
T(n)=
T(n)= 2n log n +
MSI 1 U-FOAD 27
Méthode itérative:
Equations récursives
T(1)=1
T(n) = 2n+1+2T(n/2)
donc T(n/2)=n+1+2T(n/4)
T(n)=(2n+1)+(2n+2)+4T(n/4)
or T(n/4)=n/2+1+2T(n/8)
T(n)=(2n+1)+(2n+2)+(2n+4)+8T(n/8)
…
T(n)=
T(n)= 2n log n + et comme
T(n)=2nlog n + 2n-1 = O(n log n)
MSI 1 U-FOAD 28
Méthode itérative:
Equations récursives
O(k) traitements pour décomposer et fusionner une suite de longueur k
T(n) = 2 * n *[ log2 n ]
MSI 1 U-FOAD 29
Méthode générale:
Equations récursives
T(n) = a * T(n/b) + f(n)
avec a
Si ) alors T(n)= ),
Si f(n)= alors T(n)=( * log n),
Si ) et
Si * f(n) alors T(n)=
MSI 1 U-FOAD 30
Méthode par substitution:
Equations récursives
T(n) = 2n.+1+2T(n/2) et T(1)=1
Hypothèse: T(n)=O(n log n)=an log n + bn +c et donc T(n/2)=a/2
n log n + (b-a)n/2 +c
T(n)= 2n+1+2T(n/2)=2n+1+an log n+(b-a)n +2c
=an log n +(b-a+2)n +2c +1
(1) b=b-a+2 et a=2
(2) c=2c+1 et c=-1
(3) T(1)=b-a+2+2c+1=1 donc b=2
Et finalement T(n)=2n log n + 2n-1 = O(n log n)
MSI 1 U-FOAD 31
Temps de Calcul:
Simulation
Taille Log2 n n n log2 n n2 2n
10 0.003 ms 0.01 0.03 ms 0.1 ms 1 ms
ms
100 0.006 ms 0.1 ms 0.6 ms 10 ms 1014
siècles
1000 0.01 ms 1 ms 10 ms 1s
104 0.013 ms 10 ms 0.1 s 100 s
105 0.016 ms 100 1.6 s 3heur
ms es
106 0.02 ms 1s 20 s 10
MSI 1 U-FOAD jours 32
Temps de Calcul:
Simulation
nTs = nombre d’instructions par
seconde
nTs 2n n2 n log2 n n log2 n
106 20 1000 63000 106 10 300000
107 23 3162 600000 107 103000000
109 30 31000 4.107 109
1012 40 106 3.1010
MSI 1 U-FOAD 33
