Algorithmes Complexit e Conclusion
Complxit des algorithmes e e
Pr. Mohamed EL ANSARI
Dpartement dInformatique e Facult des Sciences, Universit Ibn Zohr e e Agadir
melansari@[Link]
Fili`re: SMI4 e Module: Algorithmes & Structures de donnes e
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Plan
1
Algorithmes Reprsentations des algorithmes e Codage dun algorithme Oprations lmentaires e ee Complexit e Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e Conclusion
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Reprsentations des algorithmes e Codage dun algorithme Oprations lmentaires e ee
Algorithmes
Le mot algorithme vient du nom du mathmaticien arabe Al Khuwarizmi. Un algorithme est une suite de traitement lmentaires ee pouvant tre excutes automatiquement. e e e Un algorithme prend en entre des donnes et produit un e e rsultat. e Une recette de cuisine est un algorithme, lentre tant les e e ingrdients et la sortie le plat cuisin. e e Lalgorithme dEuclide: cest un algorithme permettant de dterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers.
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Reprsentations des algorithmes e Codage dun algorithme Oprations lmentaires e ee
Reprsentations des algorithmes e
Un programme est la ralisation dun algorithme (traduction e en un language de programmation ` savoir C/C++, Pascal, a Fortran, Java, ...etc). Pour dcrire la solution dun probl`me, on utilise les e e algorithmes an de saranchir des langages de programmation. Lalgorithme sera par la suite traduit au langage souhait. e Il y a deux types de reprsentations pour les algorithmes: e
1 2
Un pseudo langage (pseudo-code) Un organigramme
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Reprsentations des algorithmes e Codage dun algorithme Oprations lmentaires e ee
Pseudo langage
Structures lmentaires dun pseudo langage: ee
1 2 3
Entres/Sorties: LIRE, ECRIRE e Aectation: X Y Instructions conditionnelles:
Si condition Alors instructions FinSi Si condition Alors instructions1 Sinon instructions2 FinSi
Instructions rptitives (les boucles) e e
TantQue condition Faire instructions FinTantQue Faire instructions TantQue condition Pour i=0 ` n Faire instructions FinPour a
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Reprsentations des algorithmes e Codage dun algorithme Oprations lmentaires e ee
Pseudo langage
Exemple
Exemple: Calculer la factorielle de N. Version itrative e
1 2 3
LIRE N F 1 Pour I=1 ` N Faire a F F I FinPour ECRIRE F
NB. Il nexiste pas de formalisme universel pour lcriture dun e pseudo programme.
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Organigramme
Un organigramme permet de reprsenter graphiquement un algorithme. e Organigramme de la factorielle
Algorithmes Complexit e Conclusion
Reprsentations des algorithmes e Codage dun algorithme Oprations lmentaires e ee
Codage dun algorithme
Traduire lalgorithme dans un langage de programmation pour pouvoir lexcuter sur un ordinateur. e Chaque instruction lmentaire sera traduite dans le langage ee de programmation. Il faut choisir la faon de reprsenter les donnes (structures c e e de donnes). e Pour rsoudre un probl`me: nombreux algorithmes possibles. e e Pour chaque algorithme: plusieurs choix de structures de donnes. e
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Reprsentations des algorithmes e Codage dun algorithme Oprations lmentaires e ee
Oprations lmentaires e ee
Etant donn un algorithme, nous appelons oprations e e lmentaires: ee
1 2 3
un acc`s en mmoire pour lire ou crire la valeur dune variable; e e e une opration arithmtique entre deux variables: +,- ...etc; e e une comparaison entre deux variables.
Considrons par exemple linstruction c a + b. Elle fait e appel ` quatre oprations lmentaires: a e ee
1 2 3 4
lacc`s en mmoire pour lire la valeur de a, e e lacc`s en mmoire pour lire la valeur de b, e e laddition de a et b, lacc`s en mmoire pour crire la nouvelle valeur de c. e e e
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Notions de complexit e
Plusieurs algorithmes permettent de rsoudre un mme e e probl`me. e Exemple: Pour trier les lments dun tableau il y a dirents ee e algorithmes:
1 2 3 4 5
tri par slection, e tri par insertion, tri rapide, tri par fusion, ....
Comment valuer les performances dun algorithme? e Sur quel crit`re il faut se baser pour choisir le meilleur e algorithme?
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Notions de complexit e
La complexit dun algortithme est une valuation du cot de e e u lalgorithme en termes de:
1 2
temps dexcution (complexit temporelle) ou e e despace mmoire (complexit spatiale, encombrement en e e mmoire des donnes) e e
On va traiter dans la suite la complexit temporelle. Les e mmes notions permettent de traiter la complexit spatiale. e e La complexit permet de dterminer si un algorithme A et e e meilleur quun algorithme B.
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Complexit en temps e
Complexit = temps de calcul et mmoire requis pour obtenir e e un rsultat donn. e e Bonne ma trise de la complexit se traduit par: e
1 2
temps de calcul des applications prvisible, e mmoire occupe par lapplication est contrle. e e oe des latences importantes dans les temps de calcul, des dbordements mmoire, e e consquence : planter la machine. e
Mauvaise comprhension de la complexit dbouche sur: e e e
1 2 3
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Complexit en temps e
Lvaluation exacte du temps de calcul dpend de nombreux e e param`tres: e
1 2 3 4 5
le langage utilis pour coder lalgorithme. e le compilateur utilis. e lordinateur sur lequel va tourner le programme (sa rapidit). e taille et structure de donnes. e ....
Objectif: comparer plusieurs algorithmes permettant de rsoudre un mme probl`me lorsque la taille des donnes e e e e manipules devient grande. e Nous sommes plus intresss par un comportement e e asymptotique: que se passe-til quand la taille des donnes e tend vers linni?
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Complexit en temps e
Dnitions e
Dnition de la complexit dun algorithme e e Soit A un algorithme et d une donne dentre de A. On appelle e e complexit de A pour d, note CA (d), le nombre doprations e e e lmentaires eectues lors de lexcution de A sur d. ee e e Le nombre doprations est exprim en fonction de param`tres e e e associs aux instances ` traiter. e a Exemple: la complexit dun tri est fonction du nombre de e donnes ` trier. La complexit nest pas la mme avec deux e a e e jeux de donnes dirents ` savoir: e e a
rapide si des donnes sont dj` tries. e ea e moins rapide si les donnes sont dsordonnes. e e e
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Types de complexit e
1
La complexit dans le pire des cas: on consid`re le plus grand e e nombre doprations lmentaires eectues sur les donnes. e ee e e On cherche un majorant de la complexit e (SupA (n) = sup{CA (d)/d de taille n}). Cest la mesure la plus utilise. e La complexit dans le meilleur des cas: on consid`re le plus e e petit nombre doprations lmentaires eectues sur les e ee e donnes (InfA (n) = inf {CA (d)/d de taille n}). e La complexit en moyenne: la moyenne des nombres e doprations lmentaires eectues sur tous les jeux des e ee e donnes. Ce calcul est gnralement dicile ` formuler car il e e e a faut conna la probabilit de chacun des jeux de donnes tre e e pour un calcul pertinent de cette moyenne (MoyA (n) = d de taille n p(d) CA (d)).
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Calcul de la complexit dans le pire des cas: exemple-1 e
Exemple-1 1. K 0 2. I 0 3. TantQue I N Faire
a. R R + [I ] b. I I + 1
4. FinTantQue Supposons que (avec t1, t2, t3, et t4 sont des constantes): t1: temps dexcution des instructions 1-2. e t2: temps dexcution de linstruction 3 (comparaison). e t3: temps dexcution de linstructions a. e t4: temps dexcution de linstructions b. e
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Calcul de la complexit dans le pire des cas: exemple-1 e
Le temps dexcution t(n) pour N = n scrit: e e n (t2 + t3 + t4) + t2 t(n) = t1 + i =1 Soit tit le temps dexcution dune itration dni par e e e tit = t2 + t3 + t4 alors t(n) = t1 + t2 + n tit Le temps dexcution dpend linairement de la taille n e e e (fonction ane). Comportement asymptotique: valeur de t(n) quand n tend vers linni? t(n) est quivalente ` tit n lorsque n tend ` linni. e a a Lalgorithme est donc asymptotiquement linaire en n. e
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Notations en O
Domination asymptotique Soient f et g deux fonctions de N dans R+ , Si c R+ et n0 N tels que, pour tout n > n0 , f (n) c g (n) on dit que f est en O(g ) (f est asymptotiquement domine par g ) e Exemple f (n) = 3n + 1, g (n) = n alors 3n + 1 est en O(n). En eet pour n0 = 2 et c = 4 on a 3n + 1 4n pour n > n0
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Notations en
Ordre de grandeur Soient f et g deux fonctions de N dans R+ , Si f est en O(g ) et g est en O(f ) alors on dit que f est en (g ) (f et g sont de mme e ordre de grandeur asymptotique) Exemple f (n) = 3n + 1, g (n) = n alors 3n + 1 est en (n). En eet dune part 3n + 1 est en O(n), dautre part pour n0 = 2 et c = 2 on a n 2 (3n + 1) pour n > n0 et donc n est en O(3n + 1)
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Proprits ee
f est en (g ) si et seulement si c R+ , d R+ , n0 N tels que n N , n > n0 d g (n) f (n) c g (n) La notation se ram`ne ` un encadrement (` partir dun e a a certain rang) de la quantit f . e Si Lim
n f (n) g (n) f (n) g (n) f (n) g (n)
= a = 0 f est en (g ) = 0 f est en O(g ) mais f nest pas en (g ) = f nest pas en O(g ) et donc f nest
Si Lim
n
Si Lim
n
pas en (g )
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Proprits ee
En pratique: La fonction f reprsente une quantit ` tudier (temps, e eae nombre doprations). e La fonction g fait partie dune chelle de fonctions simples e 2 , etc...) destine ` informer sur le (n, n log2 (n), n e a comportement asymptotique de f . Les proprits cites ci-dessus permettent dans la pluspart des ee e cas dvaluer f . On cherche lquivalent de f ` linni. e e a Exemple: f (n) = 3n + 1, 3n+1 3n et donc
Lim
n
3n+1 n
= 3 = 0 (3n + 1) est en (n)
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Rgles de calcul de la complexit (en pire) e e
La complexit est value en temps ou en nombre doprations e e e e dun algorithme. Les r`gles gnrales sont: e e e Le temps dexcution (TE) dune aectation ou dun test est e considr comme constant c. ee Le temps dune squence dinstructions = la somme des TE e des instructions qui la composent. Le temps dun branchement conditionnel = TE du test + le max des deux TE correspondant aux deux alternatives. Le temps dune boucle = (le cot du test + le cot du corps u u de la boucle)*(nombre ditrations) + le test de la sortie de la e boucle.
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Exemples de calcul de la complexit e
Deux boucles imbriques sans dpendance des indices e e
Donner la complexit de lalgorithme suivant: e
Algorithme B0 I1 TantQue I N Faire Soit Op(n) le nombre doprations e lmentaires, avec N = n ee Op(n) = 1 + 1 +
n i=1
1+2+1+
2
n j=1
(1 + 3) + 1 +
B B+2 J1 TantQue J N Faire
T[i,j] (1+T[j,i])*B
1 = 3 + 5n + 4n 2 Limn 3+5n+4n = 4 Op(n) est n2 en (n2 )
FinTantQue
FinTantQue
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Exemples de calcul de la complexit e
Deux boucles imbriqus avec indpendance des indices e e
Donner la complexit de lalgorithme ci-dessous: e Algorithme B 0 I 1 TantQue I N Faire
B B+2 J 1 TantQue J I Faire
T[I,J] (1+T[J,I])*B J J+1
Solution:?
FinTantQue
I I+1 FinTantQue
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Complexit dun algorithme rcursif e e
Soit lalgorithme: Factorielle dun entier fonction factorielle(n:entier):entier dbut e
si n=0 alors
retourner 1
sinon
retourner n*factorielle(n-1)
sinon
n
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Complexit dun algorithme rcursif e e
Solution: c1 : temps dexcution pour le test et c2 : le temps dexcution e e pour la multiplication. T (n = 0) = c1 T (n) = c1 + c2 + T (n 1) T (n) = n c2 + (n + 1) c1 Complexit O(n) e Les calculs de la complexit rcursive induisent naturellement des e e suites.
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Echelle de complexit e
Nous donnerons ici les ordres de grandeur et leur correspondance: O(1) : constante. une instruction simple ou nombre ni dinstructions. O(log (n)) : logarithmique. Quand on part dun grand probl`me ` un sous-probl`me plus petit par rduction. e a e e O(n) : linaire, e n log (n) O(n2 ), O(n3 ), O(np ) : polynomiales, O(p n ) : exponentielle.
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Notions de complexit e Complexit en temps e Types de complexit e Notations en O Notations en Complexit dun algorithme rcursif e e Echelle de complexit e
Inuence de la complexit e
Le tableau ci-dessous donne le temps dexcution de cinq e algorithmes selon leur comportement et la taille des donnes; on e suppose que la dure dune instruction est de lordre de 1s. e Taille (n=) 10 100 1000 10000 100000 log(n) 3s 7s 10s 13s 17s n 10s 100s 1000s 1/100s 1/10s n*log(n) 30s 700s 1/100s 1/7s 2s n2 100s 1/100s 1s 1,7mn 2,8h 2n 1000s 1014 si`cles e astronomique astronomique astronomique
Table: Temps dexcution des dirents algorithmes e e
Pr. Mohamed EL ANSARI Complxit des algorithmes e e
Algorithmes Complexit e Conclusion
Conclusion
Probl`me Algorithme Programme Solution. e Quel algorithme? Quelle structure de donnes? e Comment juger un algorithme? Complexit? Comment la calculer? e
Pr. Mohamed EL ANSARI
Complxit des algorithmes e e
