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](https://pdfprof.com/Listes/17/22513-17complexite-cm.pdf.pdf.jpg)
Complexité des algorithmes
Stéphane Grandcolas
stephane.grandcolas@univ-amu.fr Cours complexité - Stéphane Grandcolas - p. 1/28Algorithmes
P: un problème
M: une méthode pour résoudre le problèmePAlgorithme : description de la méthodeMdans un
langage algorithmiquedu nom du mathématicien perseAl Khuwarizmi(780 - 850) Cours complexité - Stéphane Grandcolas - p. 2/28Structures 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/28Complexité 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/28Complexité 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/28Evaluation 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/28Evaluation deT(n)(embranchement)
Max des coûts.
siTraitement1T1(n)
sinon max(T1(n),T2(n)) Cours complexité - Stéphane Grandcolas - p. 7/28Evaluation deT(n)(boucle)
Somme des coûts des passages successifs
tant queTraitementTi(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)alors2FunctionRecursive(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/28Notation de LandauO(f(n))
c f(n)x 0nnT(n) = O(f(n))
Caractérise le comportement asymptotique (i.e. quandn→ ∞). Cours complexité - Stéphane Grandcolas - p. 10/28NotationΘ(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/28Exemples
f(n) =n3+ 2n2+ 4n+ 2 =O(n3) Cours complexité - Stéphane Grandcolas - p. 12/28Exemples
f(n) =n3+ 2n2+ 4n+ 2 =O(n3) f(n) =nlogn+ 12n+ 888 =O(nlogn) Cours complexité - Stéphane Grandcolas - p. 12/28Exemples
f(n) =n3+ 2n2+ 4n+ 2 =O(n3) f(n) =nlogn+ 12n+ 888 =O(nlogn) f(n) = 1000n10-n7+ 12n4+2n1000=O(2n)
Cours complexité - Stéphane Grandcolas - p. 12/28 Les principales classes de complexitéO(1)temps constantO(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/28Exemple : permutation
fonctionpermutation(S,i,j)1tmp:=S[i], coûtc12S[i] :=S[j],
coûtc23S[j] :=tmp,
coûtc34renvoyerS
coûtc4Coût total
T(n) =c1+c2+c3+c4=O(1)
Cours complexité - Stéphane Grandcolas - p. 14/28Exemple : 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/28Exemple : 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/28Equations récursives
Boucles itératives, fonctions récursives (approches de type diviser pour régner notamment)Cas généralT(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 intuitionT(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-13si(x > S((g+d)/2))alors
g <(g+d)/2< d4g:= (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/28Mé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/28Mé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/28Méthode itérative[Equations récursives]
T(1) = 1
T(n) = 2n+ 1 + 2T(n/2)
Cours complexité - Stéphane Grandcolas - p. 23/28Mé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/28Mé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/28Mé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/28Mé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) + 2lognT(n) = 2nlogn+?logn-1
i=02i+n Cours complexité - Stéphane Grandcolas - p. 23/28Mé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) + 2lognT(n) = 2nlogn+?logn-1
i=02i+n et commePni=02i= 2n+1-1, on aPlogn-1 i=02i= 2logn-1T(n) = 2nlogn+ 2n-1 =O(nlogn)
Cours complexité - Stéphane Grandcolas - p. 23/28Mé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 longueurkT(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/28Temps de calcul[simulation]
Taille
log2n n nlog2n n2 2n 100.003ms
0.01ms
0.03ms
0.1ms 1ms 1000.006ms
0.1ms 0.6ms 10ms1014siecles
10000.01ms
1ms 10ms 1s 1040.013ms
10ms 0.1s 100s105
0.016ms
100ms1.6s
3heures
1060.02ms
1squotesdbs_dbs29.pdfusesText_35[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