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 ∃𝑐1, 𝑐2, 𝑛𝑜 tels que ∀𝑛>no, 𝑐1 ∗ 𝑓(𝑛) ≤ 𝑐2 ∗ 𝑓(𝑛)
MSI 1 U-FOAD 11
EXEMPLES
f(n)=n3+2n2+4n+2=O(n3) (si n≥ 1 𝑎𝑙𝑜𝑟𝑠 𝑓 𝑛 ≤ 8 ∗ 𝑛3)
f(n)=n log n+12n+888 = O(n log n)
𝑛
2
f(n)=1000n10-n7+12n4+100 = 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
𝐶𝑝𝑒𝑟𝑚 ∗𝑛∗(𝑛−1)
T(n) = Cperm+σ𝑛−1
𝑖=1 𝑖 = =𝑂(𝑛2 )
2
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, g < 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 ≤ 𝑑
2 tant que (g < 𝑑 − 1) faire stoppe quand g = 𝑑 − 1
𝑔+𝑑
3 si(x > 𝑆(𝑔+𝑑) alors g< <𝑑
2
2
4 g := (g+d)/2, et donc g < 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 ≤ 𝑑
5 Sinon
6 d := (g+d)/2 et donc g < 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 ≤ 𝑑
7 Renvoyer d, et donc g < 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 ≤ 𝑑 𝑒𝑡 𝑔 = 𝑑 − 1
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
𝑛−1 𝑛 ∗ (𝑛 − 1)
𝑖= = 𝑜(𝑛2)
𝑖=1 2
𝑛 𝑛+1 − 1
𝑥
𝑥𝑖 =
𝑖=0 𝑥−1
𝑛
2𝑛+1 − 1
𝑖=0
MSI 1 U-FOAD 21
Méthode itérative:
Equations récursives
fonction TriParFusion (S,n)
1 si(n≤ 1) 𝑎𝑙𝑜𝑟𝑠
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)
…
log 𝑛−1
T(n)=σ𝑖=0 2𝑛 + 2𝑖 + 2log 𝑛
MSI 1 U-FOAD 26
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)
…
log 𝑛−1
T(n)=σ𝑖=0 2𝑛 + 2𝑖 + 2log 𝑛
log 𝑛−1 𝑖
T(n)= 2n log n + 𝑖=0
σ 2 +𝑛
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)
…
log 𝑛−1
T(n)=σ𝑖=0 2𝑛 + 2𝑖 + 2log 𝑛
log 𝑛−1 𝑖
T(n)= 2n log n + 𝑖=0
σ 2 + 𝑛 et comme
+ 1 − 1, log 𝑛
σ𝑛𝑖=0 2𝑖
= 2 𝑛 𝑎 𝑜𝑛 σlog
𝑖=0
𝑛−1 𝑖
2 =2 −1
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≥ 1, 𝑏 > 1 𝑒𝑡 𝑓 𝑛 𝑒𝑠𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑎𝑠𝑦𝑚𝑝𝑡𝑜𝑡𝑖𝑞𝑢𝑒𝑚𝑒𝑛𝑡
Si ∃∈> 0, 𝑓 𝑛 = 0(𝑛logb 𝑎−∈ ) alors T(n)=𝜃(𝑛𝑙𝑜𝑔𝑏 𝑎 ),
Si f(n)=𝜃(𝑛𝑙𝑜𝑔𝑏 𝑎 ) alors T(n)=𝜃(𝑛𝑙𝑜𝑔𝑏 𝑎 * log n),
Si ∃𝑐 > 0, 𝑓 𝑛 = Ω(𝑛𝑙𝑜𝑔𝑏 𝑎+∈ ) et
𝑛
Si ∃∈< 1, ∃𝑛0, ∀𝑛 > 𝑛0, 𝑎 ∗ 𝑓(𝑏 ) ≤ 𝑐 * 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 ms 0.03 ms 0.1 ms 1 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 ms 1.6 s 3heures
106 0.02 ms 1s 20 s 10 jours
MSI 1 U-FOAD 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
