Algorithmique...

Complexit

Luc Brunluc.brun@greyc.ensicaen.fr

A partir de travaux deHabib Abdulrab(Insa de Rouen)

Complexite p.1/25

Plan...Notion de complexitComment valuer la complexit dun algorithmeExemple de calculs de complexit

Complexite p.2/25

Notion de complexit (1)Comment valuer les performances dun algorithmediffrents algorithmes ont des cots diffrents en termes de

temps dexcution (nombre doprations effectues par lalgorithme),taille mmoire (taille ncessaire pour stocker les diffrentes structures dedonnes pour lexcution).

Ces deux concepts sont appel la complexit en temps et en espace delalgorithme.

Complexite p.3/25

Notion de complexit (2)La complexit algorithmique permet de mesurer les performances dunalgorithme et de le comparer avec dautres algorithmes ralisant les mmefonctionnalits.La complexit algorithmique est un concept fondamental pour toutinformaticien, elle permet de dterminer si un algorithme a et meilleurquun algorithme b et sil est optimal ou sil ne doit pas tre utilis. . .

Complexite p.4/25

Temps dexcution (1)Le temps dexcution dun programme dpend :1. du nombre de donnes,2. de la taille du code,3. du type dordinateur utilis(processeur,mmoire),4. de la complexit en temps de lalgorithme abstrait sous-jacent.

Complexite p.5/25

Temps dexcution (2)Soit n la taille des donnes du problme et T (n) le temps dexcution delalgorithme. On distingue :

Le temps du plus mauvais cas Tmax(n):Correspond au temps maximum pris par lalgorithme pour un problme detaille n.Le temps moyen Tmoy :Temps moyen dexcution sur des donnes de taille n ( suppositions surla distribution des donnes).

Tmoy(n) =r

i=1

piTsi(n)

pi probabilit que linstruction si soit excute,Tsi(n) : temps requis pour lexcution de si.

Complexite p.6/25

Temps dexcutionRgles gnrales :1. le temps dexcution (t.e.) dune affectation ou dun test est considr

comme constant c,

2. Le temps dune squence dinstructions est la somme des t.e. desinstructions qui la composent,

3. le temps dun branchement conditionnel est gal au t.e. du test plus le maxdes deux t.e. correspondant aux deux alternatives (dans le cas dun tempsmax).

4. Le temps dune boucle est gal la somme du cot du test + du corps de laboucle + test de sortie de boucle.

Complexite p.7/25

Problmes du temps dexcution (1)Soit lalgorithme suivant :

Nom: Calcul dune somme de carrsRole: Calculer la valeur moyenne dun tableauEntre: n : entierSortie: somme : relDclaration: i: Natureldbut

somme 0.0pour i0 n-1 faire

somme somme+i*ifinpour

finComplexite p.8/25

Problmes du temps dexcution (2)

Tmoy(n) = Tmax(n) = c1 + c1 + n(c2 + c3 + c4 + c5 + c1)

= 2c1 + n(5

i=1 ci

)

avec c1 : affectation, c2 : incrmentation, c3 test, c4 addition, c5 multiplication.

Trop prcis 1. Faux,2. Inutilisable.

Notion de complexit : comportement asymptotique du t.e.:

Tmax(n) = Tmoy(n) nC

Complexite p.9/25

Estimation asymptotiqueDfinition 1 Une fonction f est de lordre de g , crit avec la notation Grand-Ocomme: f = O(g) , sil existe une constante c et un entier n0 tels que:f(n) cg(n), pour tout n n0selon la dfinition ci-dessus, on aura:

f1(n) = 2n + 3 = O(n3), 2n + 3 = O(n2), 2n + 3 = O(n)au plus juste

f2(n) = 7n2 = O(2n), 7n2 = O(n2) au plus juste

mais, 7n2 NEST PAS O(n)

Complexite p.10/25

galit de complexitDfinition 2 2 fonctions f et g sont dgale complexit, ce qui scrit comme:O( f )= O( g ) (ou f = (g)), ssi f = O(g) et g = O(f)exemples:

n, 2n , et 0, 1n sont dgale complexit: O(n) = O(2n) = O(0, 1n)O(n2) et O(0, 1n2 + n) sont dgale complexit: O(n2) = O(0, 1n2 + n)par contre: 2n et n3 se sont PAS dgale complexit: O(2n) 6= O(n3)

Dfinition 3 une fonction f est de de plus petite complexit que g, ce qui scritcomme: O(f) < O(g) , ssi f = O(g) mais g 6= O(f)exemples:

100n est de plus petite complexit que 0, 01n2 : O(100n)< O(0, 01n2),log2 n est de plus petite complexit que n: O(log2 n) < O(n),par contre: 0, 1n2 nest PAS de plus petite complexit que 10n2 : O(0, 1n2)= O(10n2)

Complexite p.11/25

PropritsRflexivit:

g = O(g)

Transitivit :

si f = O(g) et g = O(h) alors f = O(h)

Produit par un scalaire :O(f) = O(f), > 0.Somme et produit de fonctions :O(f)+O(g)=O(max{f, g})

O(f).O(g)=O(f.g)

Complexite p.12/25

Complexit dune bouclepour i1 n faire

sfinpouravec s=O(1).

Temps de calcul de s: Ts = CNombre dappels de s : nTemps de calcul total : T (n) = nTs = O(n)Complexit : O(n)

Complexite p.13/25

Boucles imbriquesThorme 1 La complexit de p boucles imbriques de 1 n ne contenant quedes instructions lmentaires est en O(np).Preuve:

vrai pour p = 1,supposons la ppt vrai lordre p. Soit :pour i1 n faire

instructionfinpouro instruction contient p boucles imbriques.Soit Tinst(n) le temps dexcution de instruction et T (n) le temps total.T (n) = nTinst(n) avec Tinst(n) Cn

p pour n n0 (par hypothse).T (n) Cnp+1 T (n) = O(np+1)

Complexite p.14/25

Boucles tant queh 1tant que h n faire

h 2*hfintantque

Test, multiplication, affectation : O(1) : T = CNombre ditrations : log2(n).Temps de calcul : T (n) = C log2(n) = O(log2(n))

Complexite p.15/25

Complexit dun algorithme rcursif (1)Soit lalgorithme :fonction factorielle (n: Naturel) : Natureldbut

si n = 0 alorsretourner 1

sinonretourner n*factorielle(n-1)

finsifin

Complexite p.16/25

Complexit dun algorithme rcursif (2)c1 test, c2 multiplication.

T(0)=c1T(n)=c1+c2+T(n-1)

T (n) = nc2 + (n + 1)c1

Soit C = 2max{c1, c2}

T (n) Cn + c1 = O(n)

Complexit en O(n).

Les calculs de complexit dalgorithmes rcursifs induisent naturellement dessuites.

Complexite p.17/25

Algorithmes rcursifs en O(log2(n)) (1)Thorme 2 Soient, debut, fin et n = fin debut trois entiers. La complexitde lalgorithme ci dessous est en O(log2(n)).procdure f (debut,fin)

Dclaration Entiermilieudbut

milieu debut+fin2

si fin-milieu > 1 et milieu-debut > 1 alorss

sinonsi test alors

f (debut,milieu)sinon

f (milieu,fin)finsi

finsifin Complexite p.18/25

Algorithmes rcursifs en O(log2(n)) (2)Tests, s : O(1)

T (n) = T (n2) + C

T (n2) = T (n

4) + C

.

.

. =.

.

.

T (1) = T (0) + C

T (n) = T (0) + Clog2(n)

Complexite p.19/25

Algorithmes rcursifs en O(n log2(n)) (1)procdure f (debut,fin)

Dclaration Entier milieudbut

milieu debut+fin2

si fin-milieu > 1 et milieu-debut > 1 alorss1

sinonpour i1 n faire

s2finpourf(dbut,milieu)f(milieu,fin)

finsifin

Complexite p.20/25

Algorithmes rcursifs en O(n log2(n)) (2)Tests, s : O(1)Boucle : O(n).

T (n) = n + 2T (n2)

2T (n2) = n + 4T (n

4)

.

.

. =.

.

.

2p1T (2) = n + 2pT (1)

T (n) = n p + 2p T (1)

avec p = [log2(n)].On a de plus:

O(n log2(n) + nT (1)) = O(n log2(n))

Complexite p.21/25

Principales complexitsO(1) : temps constant,O(log(n)) : complexit logarithmique (Classe L),O(n) : complexit linaire (Classe P),O(n log(n))

O(n2),O(n3),O(np) : quadratique, cubique,polynomiale (Classe P),O(pn) complexit exponentielle (Classe EXPTIME).O(n!) complexit factorielle.

Complexite p.22/25

Influence de la complexitn 2n.

O(1) O(log2(n)) O(n) O(n log2(n)) O(n2) O(n3) O(2n)

t t + 1 2t 2t + 2n 4t 8t t2

1 log2(n) n n log2(n) n2 n3 2n

n = 102 1s 6s 0.1ms 0.6ms 10ms 1s 4 1016a

n = 103 1s 10s 1ms 10ms 1s 16.6min

n = 104 1s 13s 10ms 0.1s 100s 11, 5j

n = 105 1s 17s 0.1s 1.6s 2.7h 32a

n = 106 1s 20s 1s 19.9s 11, 5j 32 103a

Complexite p.23/25

Limites de la complexitLa complexit est un rsultat asymptotique : un algorithme en O(Cn2) peuttre plus efficace quun algorithme en O(C n) pour de petites valeurs de nsi C C ,Les traitements ne sont pas toujours linaires Il ne faut pas supposerdordres de grandeur entre les diffrentes constantes.

Complexite p.24/25

ConseilsQualits dun algorithme :1. Maintenable (facile comprendre, coder, dboguer),2. Rapide

Conseils :

1. Privilgier le point 2 sur le point 1 uniquement si on gagne en complexit.2. ce que fait lalgorithme doit se lire lors dune lecture rapide : Une ide

par ligne. Indenter le programme.3. Faire galement attention la prcision, la stabilit et la scurit.

La rapidit dun algorithme est un lment dun tout dfinissant les qualits decelui-ci.

Complexite p.25/25

Algorithmique...Plan...Notion de complexit{'e} (1)Notion de complexit{'e} (2)Temps d'ex{'e}cution (1)Temps d'ex{'e}cution (2)Temps d'ex{'e}cutionProbl{`e}mes du temps d'ex{'e}cution (1)Probl{`e}mes du temps d'ex{'e}cution (2)Estimation asymptotique{'E}galit{'e} de complexit{'e}Propri{'e}t{'e}sComplexit{'e} d'une boucleBoucles imbriqu{'e}esBoucles tant queComplexit{'e} d'un algorithme r{'e}cursif (1)Complexit{'e} d'un algorithme r{'e}cursif (2)Algorithmes r{'e}cursifs en complex {log _2(n)} (1)Algorithmes r{'e}cursifs en complex {log _2(n)} (2)Algorithmes r{'e}cursifs en complex {nlog _2(n)} (1)Algorithmes r{'e}cursifs en complex {nlog _2(n)} (2)Principales complexit{'e}sInfluence de la complexit{'e}Limites de la complexit{'e}Conseils