[PDF] Complexité des algorithmes Cours complexité – Stéphane Grandcolas –





Previous PDF Next PDF



Complexité dun algorithme

Pour les boucles while on doit majorer le nombre de répétions de la boucle de la même façon qu'on démontre sa terminaison. Page 7. 7 / 18. II Applications : 



Complexité algorithmique

9 sept. 2021 le cas de boucles imbriquées on calculera d'abord la complexité de la boucle interne car on en a besoin pour.



Complexité dun algorithme I Généralités

Complexité : • L'affectation c = 0 compte pour une opération élémentaire (on dit qu'elle est en O(1) car majorée par une constante). • La boucle bornée for 



Complexité des algorithmes itératifs Notations asymptotiques

Dans le meilleur des cas on rentre une seule fois dans la boucle “while” et donc la complexité est ?(n). Cela correspond `a un tableau trié par ordre croissant 



Complexité des algorithmes

Cours complexité – Stéphane Grandcolas – p. Evaluation de T(n) (boucle) ... Boucles itératives fonctions récursives (approches de type diviser pour.



1. BOUCLES ET COMPLEXITE

BOUCLES ET COMPLEXITE. A. Le langage de programmation Java. Java est un langage de programmation normalisé. Le mot Java est une marque déposée par la firme 



Cours Complexité algorithmique (MBDS) Outline

Un algorithme est dit « optimal » si sa complexité est la complexité minimale parmi les algorithmes de sa classe. 16. Complexité algorithmique. 0-notation ( 





COMPLEXITÉ ALGORITHMIQUE

Je remercie également Pascal Koiran pour m'avoir donné le goût de la recherche en complexité. Je l'ai dit ce livre doit beaucoup à l'ouvrage d'Arora et Barak



Complexité des algorithmes : nombres_instructions élémentaires

Calculer le nombre d'instructions ´el´ementaires. Boucle Pour. Comment définir le nombre d'instructions associé `a des boucles ”Pour” de la forme :.



[PDF] COMPLEXITÉ ALGORITHMIQUE - Irif

Le projet de ce livre a germé au cours d'un groupe de lecture de l'excellent ouvrage d'Arora et Barak [AB09] Une conjonction de plusieurs facteurs m'a 



[PDF] Complexité algorithmique - MIS

Objectifs des calculs de complexité : - pouvoir prévoir le temps d'exécution d'un algorithme - pouvoir comparer deux algorithmes réalisant le même 



[PDF] Calculs de complexité dalgorithmes

Complexités d'un algorithme ?Un algorithme à partir d'une donnée établit un résultat ?La taille de la donnée est mesurée par un entier n ?complexité 



[PDF] Complexité algorithmique - Université Grenoble Alpes

Dans ce document nous abordons la notion de complexité algorithmique qui est une mesure de l'« efficacité » d'un algorithme Nous nous intéressons donc non 



[PDF] Complexité algorithmique - Institut de Mathématiques de Toulouse

Tout programme écrit dans un langage composé de variables entières xi (en nombre non borné) d'opération d'affectation ? d'addition + de multiplication × de 



[PDF] Complexité des algorithmes

boucle (ou itération) Structures de données constantes variables tableaux structures récursives (listes arbres graphes) Cours complexité – Stéphane 



[PDF] Cours Complexité Algorithmique - Esentn

complexité vise à répondre aux besoins d'efficacité des algorithmes(programme) 8 Chiheb-Ed dine Ben N'Cir (ESEN) Cours Comple xité Algorithmique



[PDF] Cours Complexité algorithmique (MBDS) Outline - Esentn

Cours Complexité algorithmique (MBDS) cours 1:Introduction à la complexité des algorithmes Dr Dhouha Maatar Razgallah 2017/2018



[PDF] Complexité dun algorithme I Généralités

La complexité temporelle dans le pire des cas de la fonction mystere somme d'une opération en O(1) et d'une boucle en O(np) est donc en O(np) Lycée Michelet 



[PDF] Algorithmique et complexité de calcul

Algorithmique et complexité de calcul M Eleuldj EMI Avril 2008 Chapitre I : Préliminaires Contenu 1 Notion d'algorithme 2 Efficacité des algorithmes

:
Complexité des algorithmes

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

1squotesdbs_dbs29.pdfusesText_35
[PDF] complexité algorithmique cours

[PDF] système de congruence exercice

[PDF] résoudre équation congruence

[PDF] exercice congruence

[PDF] théorème chinois pdf

[PDF] resoudre systeme congruence

[PDF] calcul consommation ampoule 100w

[PDF] consommation ampoule 60w

[PDF] combien coute une ampoule allumée

[PDF] calcul consommation ampoule led

[PDF] lumiere allumée toute la nuit consommation

[PDF] calcul de consommation électrique d'un appareil

[PDF] consommation ventilateur 40w

[PDF] consommation congelateur ancien

[PDF] consommation four electrique kwh