Complexité des algorithmes

Exercice 1 : Complexité des algorithmes (8 points) Question 1 1: On considère le code suivant, comportant deux « tant que » imbriqués On cherche à mesurer la complexité de cette imbrication en fonction de n Pour cela, on utilise la variable compteur, qui est incrémentée à chaque passage dans le « tant que » interne def procedure(n) :

SUJET + CORRIGE

UE J1BS7202 : Algorithmique et Programmation Epreuve : Examen Date : Jeudi 19 d ecembre 2013 Heure : 9 heures Dur ee : 2 heures Documents : autoris es Epreuve de M Alain Griffault SUJET + CORRIGE Avertissement {La plupart des questions sont ind ependantes { A chaque question, vous pouvez au choix r epondre par un algorithme ou bien par un

Examen d’algorithmique - IRIF

Examen d’algorithmique Mercredi 13 janvier 2016 12h{15h / Aucun document autoris e Mode d’emploi : Le bar eme est donn e a titre indicatif La qualit e de la r edaction des algorithmes et des explications sera fortement prise en compte pour la note On peut toujours supposer une question r esolue et passer a la suite

CORRECTION DE L’EXAMEN D’ALGORITHMIQUE ET COMPLEXITE

CORRECTION DE L’EXAMEN D’ALGORITHMIQUE ET COMPLEXITE Master Informatique, première année, janvier 2015 TOUS VOS DOCUMENTS SUR PAPIER SONT AUTORISES COURRIEL ET TELEPHONE SONT INTERDITS REPONDEZ AUX QUESTIONS DANS L’ORDRE NUMEROTEZ VOS REPONSES 1 Plus court chemin et programmation linéaire Considérez le graphe ci-dessous : 0 a b 1 2 4

Complexité Corrigé

Le cas tab[pos] > x se traite de la même façon, mais en considérant le tableau tab[0:(pos - 1)] detaillebn=2c,cequiconduitàunnombred’opérationsde

TD : Complexité des algorithmes

3 complexité spatiale : 3 * m 4 complexité temporelle : m-1 La complexité temporelle est toujours favorable à la représentation avec un tableau à 1 dimension La complexité spatiale l’est également tant que 3 * m < n * n, c’est à dire m < (n*n)/3 Exercice 2 Revoir poly, transparents 33, 34, et 35

Algorithmique et Structures de Données Corrigé de lexamen écrit

Algorithmique et Structures de Données Corrigé de l'examen écrit G1: monasse (at) imagine enpc G2: nicolas audebert (at) onera G3: boulc-ha (at) imagine enpc 03/04/2019 Les exercices sont indépendants Il n'est pas interdit d'utiliser votre portable pour tester vos algorithmes, mais évidemment pas le wi 1 Calcul de déterminant

Complexité des algorithmes - diluniv-mrsfr

Complexité 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 Conﬁgurations caractéristiques meilleur cas, pire des cas, cas moyen Cours complexité – Stéphane Grandcolas

Exercices et problemes dalgorithmique

L’algorithmique a donné lieu à de nombreux ouvrages remarquables depuis plus de trente ans, sur lesquels se fondent les enseignements dispensés dans les universités et écoles d’ingénieurs, et dont nous donnons une liste non exhaustive à la ﬁn de cet ouvrage L’expérience des auteurs, enseignants chevronnés dans diﬀérentes

SUJET + CORRIGE

conséquence, de complexité O(1) Reduire(T) qui retire la dernière case du tableau T , et qui met à jour la aleurv de T longueur en consé-quence, de complexité O(1) ousV supposerez également que chaque case d'un tableau contient : un champ data pour stocker les données un champ cle pour ordonner les données

Complexité des algorithmes

Stéphane Grandcolas

stephane.grandcolas@univ-amu.fr Cours complexité - Stéphane Grandcolas - p. 1/28

Algorithmes

P: un problème

M: une méthode pour résoudre le problèmeP

Algorithme : description de la méthodeMdans un

langage algorithmiquedu nom du mathématicien perseAl Khuwarizmi(780 - 850) Cours complexité - Stéphane Grandcolas - p. 2/28

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) Cours complexité - Stéphane Grandcolas - p. 3/28

Complexité des algorithmes

On veut

Evaluer l'efficacité de la méthodeM

ComparerMavec une autre méthodeM?

indépendamment de l'environnement (machine, système, compilateur, ...) Cours complexité - Stéphane Grandcolas - p. 4/28

Complexité 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. Cours complexité - Stéphane Grandcolas - p. 5/28

Evaluation deT(n)(séquence)

Somme des coûts.

Traitement1T1(n)

Traitement2T2(n)???????

T(n) =T1(n) +T2(n)

Cours complexité - Stéphane Grandcolas - p. 6/28

Evaluation deT(n)(embranchement)

Max des coûts.

sialors

Traitement1T1(n)

sinon max(T1(n),T2(n)) Cours complexité - Stéphane Grandcolas - p. 7/28

Evaluation deT(n)(boucle)

Somme des coûts des passages successifs

tant quefaire

TraitementTi(n)

fin faire??????? k i=1Ti(n) T i(n): coût de lai`emeitération souvent défini par une

équation récursive

Cours complexité - Stéphane Grandcolas - p. 8/28 Evaluation deT(n)(fonctions récursives)fonctionFunctionRecursive(n)1si(n >1)alors

2FunctionRecursive(n/2),

coûtT(n/2)

3Traitement(n),

coûtC(n)

4FunctionRecursive(n/2),

coûtT(n/2)

Equation récursive

T(n) = 2?T(n/2) +C(n)siC(n) = 1alorsT(n) =K×n

siC(n) =nalorsT(n) =K×n×logn Cours complexité - Stéphane Grandcolas - p. 9/28

Notation de LandauO(f(n))

c f(n)x 0nn

T(n) = O(f(n))

Caractérise le comportement asymptotique (i.e. quandn→ ∞). Cours complexité - Stéphane Grandcolas - p. 10/28

NotationΘ(f(n))

xc f(n)1xc f(n)2 n0n T(n)

T(n) = Θ(f(n)) si?c1,c2,n0tels que

Cours complexité - Stéphane Grandcolas - p. 11/28

Exemples

f(n) =n3+ 2n2+ 4n+ 2 =O(n3) Cours complexité - Stéphane Grandcolas - p. 12/28

Exemples

f(n) =n3+ 2n2+ 4n+ 2 =O(n3) f(n) =nlogn+ 12n+ 888 =O(nlogn) Cours complexité - Stéphane Grandcolas - p. 12/28

Exemples

f(n) =n3+ 2n2+ 4n+ 2 =O(n3) f(n) =nlogn+ 12n+ 888 =O(nlogn) f(n) = 1000n10-n7+ 12n4+2n

1000=O(2n)

Cours complexité - Stéphane Grandcolas - p. 12/28 Les principales classes de complexitéO(1)temps constant

O(logn)logarithmique

O(n)linéaire

O(n×logn)tris (par échanges)

O(n2)quadratique, polynomial

O(2n)exponentiel (problèmes très difficiles) Cours complexité - Stéphane Grandcolas - p. 13/28

Exemple : permutation

fonctionpermutation(S,i,j)1tmp:=S[i], coûtc1

2S[i] :=S[j],

coûtc2

3S[j] :=tmp,

coûtc3

4renvoyerS

coûtc4

Coût total

T(n) =c1+c2+c3+c4=O(1)

Cours complexité - Stéphane Grandcolas - p. 14/28

Exemple : recherche séquentielle

fonctionrecherche(x,S,n)1i:= 1,

2tant que((i < n)et(S[i]?=x))faire

(nfois)

3i:=i+ 1,

4renvoyer(S[i] =x)

Pire des cas :nfois la boucle

T(n) = 1 +?ni=11 + 1 =O(n)

Cours complexité - Stéphane Grandcolas - p. 15/28

Exemple : tri à bulle

fonctionTri(S,n)1pouri:=nà2faire (n-1fois)

2pourj:= 1ài-1faire

(i-1fois)

3si(S[j]> S[j+ 1])alors

4permuterS[j]etS[j+ 1]dansS,

T(n) =Cperm×n-1?

i=1i=Cperm×n×(n-1)

2=O(n2)

Cours complexité - Stéphane Grandcolas - p. 16/28

Equations récursives

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. Cours complexité - Stéphane Grandcolas - p. 17/28 Méthode par substitution[Equations récursives]

Principe

: on vérifie une intuition

T(n) =a×T(n/b) +f(n) etT(1) =c

Hypothèse

T(n) =g(n) (intuition)

Conclusion

a×g(n/b) +f(n) =g(n) etg(1) =c

à démontrer en fixant les constantes

Cours complexité - Stéphane Grandcolas - p. 18/28 Méthode par substitution[Equations récursives] fonctionRechercheDichotomique(x,?S1,...,Sn?)1g:= 0,d:=n+ 1,

2tant que(g < d-1)faire

stoppe quand g=d-1

3si(x > S((g+d)/2))alors

g <(g+d)/2< d

4g:= (g+d)/2,

5sinon

6d:= (g+d)/2,

7renvoyerd,

Nombre d'itérations

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

Cours complexité - Stéphane Grandcolas - p. 19/28 Méthode par substitution[Equations récursives]

T(n) = 1 +T(n/2) etT(1) = 1?

intuitionT(n) =O(log2n)

HypothèseT(n) =a×log2n+c

doncT(n/2) =a×log2n-a+c en substituant on aT(n) = 1 +a×log2n-a+c donc1-a+c=ceta= 1, et puisqueT(1) = 1doncc= 1 ConclusionT(n) = log2n+ 1?s'il y a un élément on fera une itération Cours complexité - Stéphane Grandcolas - p. 20/28

Méthode itérative[rappel sommations]

?n-1 i=1i=n×(n-1)

2=O(n2)

n i=0xi=xn+1-1x-1 n i=02i= 2n+1-1 Cours complexité - Stéphane Grandcolas - p. 21/28

Méthode itérative[Equations récursives]

2renvoyerS

3décomposerSenS1etS2,

(n)

3S1:=TriParFusion(S1),

(T(?n/2?))

4S2:=TriParFusion(S2),

(T(?n/2?))

5S:=fusion(S1,S2),

(n)

6renvoyerST(n) = 1 +n+ 2×T(n/2) +netT(1) = 1

Cours complexité - Stéphane Grandcolas - p. 22/28

Méthode itérative[Equations récursives]

T(1) = 1

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

Cours complexité - Stéphane Grandcolas - p. 23/28

Méthode itérative[Equations récursives]

T(1) = 1

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

doncT(n/2) =n+ 1 + 2T(n/4)

T(n) = (2n+ 1) + (2n+ 2) + 4T(n/4)

Cours complexité - Stéphane Grandcolas - p. 23/28

Méthode itérative[Equations récursives]

T(1) = 1

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

doncT(n/2) =n+ 1 + 2T(n/4)

T(n) = (2n+ 1) + (2n+ 2) + 4T(n/4)

orT(n/4) =n/2 + 1 + 2T(n/8)

T(n) = (2n+ 1) + (2n+ 2) + (2n+ 4) + 8T(n/8)...

Cours complexité - Stéphane Grandcolas - p. 23/28

Méthode itérative[Equations récursives]

T(1) = 1

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

doncT(n/2) =n+ 1 + 2T(n/4)

T(n) = (2n+ 1) + (2n+ 2) + 4T(n/4)

orT(n/4) =n/2 + 1 + 2T(n/8)

T(n) = (2n+ 1) + (2n+ 2) + (2n+ 4) + 8T(n/8)...

T(n) =?logn-1

i=0(2n+ 2i) + 2logn Cours complexité - Stéphane Grandcolas - p. 23/28

Méthode itérative[Equations récursives]

T(1) = 1

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

doncT(n/2) =n+ 1 + 2T(n/4)

T(n) = (2n+ 1) + (2n+ 2) + 4T(n/4)

orT(n/4) =n/2 + 1 + 2T(n/8)

T(n) = (2n+ 1) + (2n+ 2) + (2n+ 4) + 8T(n/8)...

T(n) =?logn-1

i=0(2n+ 2i) + 2logn

T(n) = 2nlogn+?logn-1

i=02i+n Cours complexité - Stéphane Grandcolas - p. 23/28

Méthode itérative[Equations récursives]

T(1) = 1

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

doncT(n/2) =n+ 1 + 2T(n/4)

T(n) = (2n+ 1) + (2n+ 2) + 4T(n/4)

orT(n/4) =n/2 + 1 + 2T(n/8)

T(n) = (2n+ 1) + (2n+ 2) + (2n+ 4) + 8T(n/8)...

T(n) =?logn-1

i=0(2n+ 2i) + 2logn

T(n) = 2nlogn+?logn-1

i=02i+n et commePni=02i= 2n+1-1, on aPlogn-1 i=02i= 2logn-1

T(n) = 2nlogn+ 2n-1 =O(nlogn)

Cours complexité - Stéphane Grandcolas - p. 23/28

Méthode itérative[Equations récursives]

hauteur?log2n? n/2n n/2 n/4n/4n/4n/4 n/8n/8 n/8 n/8 n/8 n/8 n/8 n/8 ....111 O(k)traitements pour décomposer et fusionner une suite de longueurk

T(n) = 2×n× ?log2n?

Cours complexité - Stéphane Grandcolas - p. 24/28 Méthode générale[Equations récursives]

T(n) =a×T(n/b) +f(n)

aveca≥1,b >1etf(n)est positive asymptotiquement. si?? >0, f(n) =O(nlogba-?)alorsT(n) = Θ(nlogba), sif(n) = Θ(nlogba)alorsT(n) = Θ(nlogba×lgn), si?? >0, f(n) = Ω(nlogba+?)et Le tri par fusion (T(n) = 2n+ 1 + 2T(n/2)) est dans le cas 2 : a=b= 2 etf(n) = 2n+ 1 = Θ(n) etT(n) = Θ(nlogn) Cours complexité - Stéphane Grandcolas - p. 25/28 Méthode par substitution[Equations récursives]

T(n) = 2n+ 1 + 2T(n/2) etT(1) = 1

Hypothèse

:T(n) =O(nlogn) =anlogn+bn+c et doncT(n/2) =a/2nlogn+ (b-a)n/2 +c T(n) = 2n+ 1 + 2T(n/2) = 2n+ 1 +anlogn+ (b-a)n+ 2c =anlogn+ (b-a+ 2)n+ 2c+ 1 (1)b=b-a+ 2eta= 2 (2)c= 2c+ 1etc=-1 (3)T(1) =b-a+ 2 + 2c+ 1 = 1doncb= 2 et finalementT(n) = 2nlogn+ 2n-1 =O(nlogn) Cours complexité - Stéphane Grandcolas - p. 26/28

Temps de calcul[simulation]

Taille

log2n n nlog2n n2 2n 10

0.003ms

0.01ms

0.03ms

0.1ms 1ms 100

0.006ms

0.1ms 0.6ms 10ms

1014siecles

1000

0.01ms

1ms 10ms 1s 104

0.013ms

10ms 0.1s 100s
105

0.016ms

100ms
1.6s

3heures

106

0.02ms

1s 20s

10jours

Cours complexité - Stéphane Grandcolas - p. 27/28

Temps de calcul[simulation]

nTs=nombre d'instructions par seconde nTs 2n n2 nlog2n n log2n 106
20 1000
63000
106

10300000

107
23
3162

600000

107

103000000

109
30
31000
4.107 109
1012
40
106

3.1010

Cours complexité - Stéphane Grandcolas - p. 28/28quotesdbs_dbs6.pdfusesText_12

[PDF] Complexité des algorithmes - diluniv-mrsfr

Complexité des algorithmes

Stéphane Grandcolas

Algorithmes

P: un problème

Algorithme : description de la méthodeMdans un

Structures algorithmiques

Structures de contrôle

Structures de données

Complexité des algorithmes

On veut

Evaluer l'efficacité de la méthodeM

ComparerMavec une autre méthodeM?

Complexité des algorithmes

Evaluation du nombre d'

Notations :

T(n): nombre d'opérations élémentaires

Configurations caractéristiques

Evaluation deT(n)(séquence)

Somme des coûts.

Traitement1T1(n)

Traitement2T2(n)???????

T(n) =T1(n) +T2(n)

Evaluation deT(n)(embranchement)

Max des coûts.

Traitement1T1(n)

Evaluation deT(n)(boucle)

Somme des coûts des passages successifs

TraitementTi(n)

équation récursive

2FunctionRecursive(n/2),

3Traitement(n),

4FunctionRecursive(n/2),

Equation récursive

T(n) = 2?T(n/2) +C(n)siC(n) = 1alorsT(n) =K×n

Notation de LandauO(f(n))

T(n) = O(f(n))

NotationΘ(f(n))

T(n) = Θ(f(n)) si?c1,c2,n0tels que

Exemples

Exemples

Exemples

1000=O(2n)

O(logn)logarithmique

O(n)linéaire

O(n×logn)tris (par échanges)

O(n2)quadratique, polynomial

Exemple : permutation

2S[i] :=S[j],

3S[j] :=tmp,

4renvoyerS

Coût total

T(n) =c1+c2+c3+c4=O(1)

Exemple : recherche séquentielle

2tant que((i < n)et(S[i]?=x))faire

3i:=i+ 1,

4renvoyer(S[i] =x)

Pire des cas :nfois la boucle

T(n) = 1 +?ni=11 + 1 =O(n)

Exemple : tri à bulle

2pourj:= 1ài-1faire

3si(S[j]> S[j+ 1])alors

4permuterS[j]etS[j+ 1]dansS,

T(n) =Cperm×n-1?

2=O(n2)

Equations récursives

T(n) =a×T(n/b) +f(n)

Principe

T(n) =a×T(n/b) +f(n) etT(1) =c

Hypothèse

T(n) =g(n) (intuition)

Conclusion

à démontrer en fixant les constantes

2tant que(g < d-1)faire

3si(x > S((g+d)/2))alors

4g:= (g+d)/2,

5sinon

6d:= (g+d)/2,

7renvoyerd,

Nombre d'itérations