RÉSOLUTION DE SYSTÈMES À DEUX INCONNUES
Exemple. 1 2 est une solution du système d'équations linéaires. 2 3 8 méthode de substitution vous permettra d'utiliser l'information contenue dans une ...
MODÈLES DE SUBSTITUTION POUR LOPTIMISATION GLOBALE
9 janv. 2013 les méthodes de déformation par modèle de substitution : la fonction de déformation définie en chaque point du maillage volumique est ...
OPTIMISATION SOUS CONTRAINTES
Exemple. Trouver le minimum et le maximum absolus de la fonction résolution d'un tel problème fait appel à la méthode dite de substitution le résultat.
Exercices de mathématiques - Exo7
Corrections d'Arnaud Bodin. Exercice 1. 1. Résoudre de quatre manières différentes le système suivant (par substitution par la méthode du pivot.
Fonctions de 2 et 3 variables
2 Extremums sous contrainte : méthode de substitution 2.2 Méthode par substitution ... Exemple. On considère la fonction f(x y)=2xy.
Complexité des algorithmes - Algorithmique 1 - 2021-2022
Evaluation de T(n) (fonctions récursives : exemple) Exemple : permutation dans un tableau ... Méthode par substitution [recherche dichotomique].
Méta-analyse des coefficients de substitution en analyse du cycle de
2.2.2.1 Méthode de substitution des processus de recyclage . Figure 2-8 : Exemple de l'application de la méthode par substitution à qualité équivalente.
Cours doptimisation
La méthode de substitution consiste simplement `a trouver les extremums de la fonction d'une variable : ˜f(x) = f(x g(x)). Exemple: Optimiser sous les
Chiffrement par substitution.
Jules César qui avait l'habitude de cette méthode pour communiquer avec ses chiffrés par substitution (comme par exemple le Chiffre de Vigenère ou le ...
Systèmes linéaires
Par exemple 2x + 3y = 6 est une équation linéaire
Complexité des algorithmes
Algorithmique 1 - 2021-2022
Stéphane Grandcolas
Aix-Marseille Université
Contact :stephane.grandcolas@univ-amu.fr
Algorithmique 1
Objectifs :
I introduire les structures de données et les techniques de conception de base de l"algorithmique, I étudier les outils d"analyse et de preuve de correction des algorithmes.Modalités de contrôle :
session 1 :NF=0;8ET+0;2CC session 2 :NF=ETContrôle continu :quatre TP évalués.
Algorithmique 1
Programme :
I algorithmes :complexité, tris, I structures de données :arbres, tas, dictionnaires, I méthodes :backtracking, programmation dynamique, I graphes :plus courts chemins, arbres couvrants. Livre de référence :Introduction à l"algorithmique, Thomas H. Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein.
Algorithmes et structures de données
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)Structure de données :manière d"organiser et de stocker
les données (supposée rendre efficace certaines opérations)Algorithmes et structures de données
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)Structure de données :manière d"organiser et de stocker
les données (supposée rendre efficace certaines opérations)Structures algorithmiques
Structures de contrôle
I séquence I embranchement (ou sélection) I boucle (ou itération)Structures de données : supports
I constantes, variables I tableaux I structures récursives (listes, arbres, graphes)Complexité des algorithmes
On veut
IEvaluer
l"efficacité de la métho deM IComparerMavec une autre méthodeM0
indépendamment de l"environnement (machine, système, compilateur, ...)Complexité des algorithmes
Evaluation du nombre d"
opérations élémentaires en fonction I de la taille des données (par ex. le nombre d"éléments à trier) I de la nature des données (provoquant par ex. la sortie d"une boucle)Notations :
I n: taille des données, IT(n): nombre d"opérations élémentaires
Configurations caractéristiques :
I meilleur cas, I pire des cas, I cas moyen.Evaluation deT(n)(séquence)
Somme des coûts.
Traitement1T1(n)
Traitement2T2(n)9
T(n) =T1(n) +T2(n)
Evaluation deT(n)(embranchement)
Max des coûts.
siTraitement1T1(n)
sinonTraitement2T2(n)9
T c(n) +max(T1(n);T2(n))Evaluation deT(n)(boucle)
Somme des coûts des passages successifs
tant queTraitementTi(n)
fin faire9 k X i=1(Ci(n) +Ti(n)) +Ck+1(n) T i(n): coût de laiièmeitération souvent défini par uneéquation récursive
Evaluation deT(n)(fonctions récursives : exemple)2FUNCTIONRECURSIVE(n=2),coût T(n=2)
3Traitement(n),coû tC(n)
4FUNCTIONRECURSIVE(n=2),coût T(n=2)
Equation récursive
T(n) =1+2T(n=2) +C(n)
siC(n) =1 alorsT(n) =Kn siC(n) =nalorsT(n) =KnlognNotation de LandauO(f(n))nn
0cf(n)
T(n) =O(f(n))Caractérise lecomp ortementasymptotique (i.e. qd n! 1).T(n) =O(f(n))si9c9n0tels que8n>n0;T(n)cf(n)
Notation(f(n))n
0T(n)c
1f(n) c 2f(n) nT(n) = (f(n))si9c1;c2;n0tels que
8n>n0;c1f(n)T(n)c2f(n)
Exemples
T(n) =n3+2n2+4n+2=O(n3)
(sin1 alorsT(n)9n3)T(n) =nlogn+12n+2=O(nlogn)T(n) =2n10+n7+12n4+2n100 =O(2n)Exemples
T(n) =n3+2n2+4n+2=O(n3)
(sin1 alorsT(n)9n3)T(n) =nlogn+12n+2=O(nlogn)T(n) =2n10+n7+12n4+2n100 =O(2n)Exemples
T(n) =n3+2n2+4n+2=O(n3)
(sin1 alorsT(n)9n3)T(n) =nlogn+12n+2=O(nlogn)T(n) =2n10+n7+12n4+2n100 =O(2n)Les principales classes de complexité
O(1)temps constant
O(logn)logarithmique
O(n)linéaire
O(nlogn)tris par comparaisons optimaux
O(n2)quadratique,p olynomial
O(n3)cubique,p olynomial
O(2n)exponentiel(p roblèmestrès difficiles)
Exemple : permutation dans un tableau
fonctionPERMUTATION(S;i;j)1tmp:=S[i],coût c12S[i] :=S[j],coût c2
3S[j] :=tmp,coût c3
4renvoyerScoûtc4
Coût total
T(n) =c1+c2+c3+c4=O(1)
Exemple : recherche séquentielle
2tant que((i 3i:=i+1,(c3)
4renvoyer(S[i] =x)( c4)
Pire des cas :nfois la boucle
T(n) =c1+c2+Pn
i=1(c3+c2) +c4=O(n) Exemple : tri à bulle
fonctionTRI_A_BULLES(S[1;:::;n]) 1pouri:=nà2faire
2pourj:=1ài1faire
3si(S[j]>S[j+1])alorsi1 fois
4PERMUTER(S;j;j+1),Cperm
T(n) = (1+Cperm)n1X
i=1i= (1+Cperm)n(n1)2 =O(n2) Equations récursives
Boucles itératives, fonctions récursives, approches de type diviser pour régner Cas général
T(n) =aT(n=b) +f(n)
Différentes techniques :
I méthode par substitution : intuition/vérification, I méthode par développ ementitératif I en utilisant le théo rèmegénéral Méthode par substitution
Principe: on vérifie uneintuition
T(n) =aT(n=b) +f(n)etT(1) =c
Intuition
T(n) =O(g(n))
A démontrer en fixant les constantes
Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Renvoieposition, la position dexs"il apparaît dansS[], la position à laquelle il faudrait l"insérer sinon
Méthode par substitution[recherche dichotomique] 2tant que(g 4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Renvoieposition, la position dexs"il apparaît dansS[], la position à laquelle il faudrait l"insérer sinon
Méthode par substitution[recherche dichotomique] 2tant que(g 4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
3i:=i+1,(c3)
4renvoyer(S[i] =x)( c4)
Pire des cas :nfois la boucle
T(n) =c1+c2+Pn
i=1(c3+c2) +c4=O(n)Exemple : tri à bulle
fonctionTRI_A_BULLES(S[1;:::;n])1pouri:=nà2faire
2pourj:=1ài1faire
3si(S[j]>S[j+1])alorsi1 fois
4PERMUTER(S;j;j+1),Cperm
T(n) = (1+Cperm)n1X
i=1i= (1+Cperm)n(n1)2 =O(n2)Equations récursives
Boucles itératives, fonctions récursives, approches de type diviser pour régnerCas général
T(n) =aT(n=b) +f(n)
Différentes techniques :
I méthode par substitution : intuition/vérification, I méthode par développ ementitératif I en utilisant le théo rèmegénéralMéthode par substitution
Principe: on vérifie uneintuition
T(n) =aT(n=b) +f(n)etT(1) =c
Intuition
T(n) =O(g(n))
A démontrer en fixant les constantes
Méthode par substitution[recherche dichotomique]2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Renvoieposition, la position dexs"il apparaît dansS[], la position à laquelle il faudrait l"insérer sinon
Méthode par substitution[recherche dichotomique] 2tant que(g 4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Renvoieposition, la position dexs"il apparaît dansS[], la position à laquelle il faudrait l"insérer sinon
Méthode par substitution[recherche dichotomique] 2tant que(g 4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Renvoieposition, la position dexs"il apparaît dansS[], la positionà laquelle il faudrait l"insérer sinon
Méthode par substitution[recherche dichotomique]2tant que(g 4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Renvoieposition, la position dexs"il apparaît dansS[], la position à laquelle il faudrait l"insérer sinon
Méthode par substitution[recherche dichotomique] 2tant que(g 4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Renvoieposition, la position dexs"il apparaît dansS[], la position à laquelle il faudrait l"insérer sinon
Méthode par substitution[recherche dichotomique] 2tant que(g 4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Renvoieposition, la position dexs"il apparaît dansS[], la position à laquelle il faudrait l"insérer sinon
Méthode par substitution[recherche dichotomique] 2tant que(g 4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
7renvoyerd,g Renvoieposition, la position dexs"il apparaît dansS[], la position à laquelle il faudrait l"insérer sinon
Méthode par substitution[recherche dichotomique] 2tant que(g 4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
à laquelle il faudrait l"insérer sinon
Méthode par substitution[recherche dichotomique]2tant que(g 4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
4g:= (g+d)=2,et donc g 5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
5sinon
6d:= (g+d)=2,et donc g 7renvoyerd,g Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
7renvoyerd,g Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
Après la boucle,d1 Méthode par substitution[recherche dichotomique] 2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
2tant que(g 3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique] Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération I T(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique] T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11 Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions 9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 7 2 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 6 3 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S 1:=TRI_PAR_FUSION(S1),
4S 2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S 1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S 2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2k Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)= Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+nor Plogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn) Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 1 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba), Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn) Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+c T(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn) Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog 2nnnlog2nn
22
14siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn 2nlog2nnlog
2n10 62010006300010
610
30000010
723316260000010
710
300000010
930310004:10710
910
124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47
3si(x>S[(g+d)=2])alors
4g:= (g+d)=2,
5sinon
6d:= (g+d)=2,
7renvoyerd,
Nombre d"itérations :T(n) =1+T(dn=2e)
A chaque itération le nombre d"éléments considérés (entre les indicesgetd) est divisé
par deux. Méthode par substitution[recherche dichotomique]Nombre d"itérations
T(n) =1+T(n=2)etT(1) =1
I T(1) =1 car s"il y a un seul élément on fera une itération IT(dn=2e) =T(n=2)
(pour simplifier on considère quenest de la forme 2k) Méthode par substitution[recherche dichotomique]T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique]T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique]T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par substitution[recherche dichotomique]T(n) =1+T(n=2)etT(1) =1
IntuitionT(n) =O(log2n)HypothèseT(n) =k1log2n+k2doncT(n=2) =k1log2nk1+k2carlog2(n=2) =log2n1 doncT(n) =1+T(n=2) =1+k1log2nk1+k2 donc 1k1+k2=k2et donck1=1, enfin, puisqueT(1) =1, on ak2=1ConclusionT(n) =log2n+1=O(log2n) (en fait(log2n)) Méthode par développement itératif : sommations I Pn1 i=1i=n(n1)2 = (n2) =O(n2) I Pn i=0xi=xn+11x1 en particulier quandxvaut 2 P n i=02i=2n+11Tri par fusion
I diviser pour régner I décomposition I fusiondécompositions9 1 5 7
1 7 2 3 9 5 1 7 9 5 5 9 1 72 3 4 6
1 5 7 9
1 2 3 4 5 6 7 9fusions
2 63 4 466 24 3 6 4 2 36 9 4 1 2 5 3 7
Tri par fusion
2décomposerS!(S1;S2),
3S1:=TRI_PAR_FUSION(S1),
4S2:=TRI_PAR_FUSION(S2),
5S:=FUSIONNER(S1;S2),
6renvoyerS
Tri par fusion
2décomposerS!(S1;S2),( n)
3S1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =1+n+T(dn=2e) +T(bn=2c) +netT(1) =1
Tri par fusion
2décomposerS!(S1;S2),( n)
3S1:=TRI_PAR_FUSION(S1),( T(dn=2e))
4S2:=TRI_PAR_FUSION(S2),( T(bn=2c))
5S:=FUSIONNER(S1;S2),( n)
6renvoyerS
T(n) =2n+1+2T(n=2)
on suppose quenest de la forme 2kMéthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)=Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+norPlogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn)Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)=Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+norPlogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn)Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)=Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+norPlogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn)Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)=Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+norPlogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn)Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)=Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+norPlogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn)Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)=Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+norPlogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn)Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)=Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+norPlogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn)Méthode par développement itératif[tri par fusion]T(n)=2n+1+2T(n=2)doncT(n=2) =n+1+2T(n=4)= (2n+1) + (2n+2) +4T(n=4)orT(n=4) =n=2+1+2T(n=8)= (2n+1) + (2n+2) + (2n+4) +8T(n=8)...
T(n)=Plogn1
i=0(2n+2i) +2lognT(1)=2nlogn+Plogn1 i=02i+norPlogn1
i=02i=2logn1=n1=2nlogn+2n1= (nlogn)Tri par fusionn/2 n/2
n/4n/4n/4n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/81 1 1 ....n
2nhauteurdlogne2n
2ndécomposition ou fusion d"une suite de longueurn=k: coûtO(n=k)
T(n) =2n dlog2ne
Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba),Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn)Master theorem[Equations récursives]
T(n) =aT(n=b) +f(n)
aveca1,b>1 etf(n)est positive asymptotiquement. I si9 >0;f(n) =O(nlogba)alorsT(n) = (nlogba),Isif(n) = (nlogba)alorsT(n) = (nlogbalogn),I
si9 >0;f(n) = (nlogba+)et si9c<1;9n0;8n>n0;af(n=b)cf(n)alors T(n) = (f(n))Tri par fusion (T(n) =2T(n=2) +2n+1) cas 2 : a=b=2 etf(n) =2n+1= (n) et doncT(n) = (nlogn)Méthode par substitution[tri par fusion]
T(n) =2n+1+2T(n=2)etT(1) =1
Hypothèse
: T(n) =O(nlogn) =anlogn+bn+c et doncT(n=2) =an=2logn+ (ba)n=2+cT(n) =2n+1+2T(n=2) =2n+1+anlogn+ (ba)n+2c
=anlogn+ (ba+2)n+2c+1 (1)b=ba+2 et donca=2 (2)c=2c+1 et doncc=1 (3)T(1) =b+c=1 et doncb=2 et finalementT(n) =2nlogn+2n1=O(nlogn)Temps de calcul[simulation]
Combien de temps pour traiter un problème?Taillelog2nnnlog2nn
2214siecles10000:01ms1ms10ms1s10
40:013ms10ms0:1s100s10
50:016ms100ms1:6s3heures10
60:02ms1s20s10jourspour une machine qui effectue 10
6traitements par seconde
Temps de calcul[simulation]
Quel problème peut-on traiter en une seconde?nTs2 nn2nlog2nnlog
2n1062010006300010
61030000010
723316260000010
710300000010
930310004:10710
910124010
63:1010nTs=nombre d"instructions effectuées chaque seconde
quotesdbs_dbs47.pdfusesText_47[PDF] Methode par substitutions
[PDF] méthode physique chimie terminale s
[PDF] méthode pivot exercices résolus
[PDF] Méthode plan en philo
[PDF] methode pour apprendre a lire a 3 ans
[PDF] Méthode pour apprendre des leçons
[PDF] methode pour apprendre l orthographe
[PDF] methode pour apprendre l'orthographe
[PDF] Méthode pour apprendre ses formules de physique-chimie
[PDF] Méthode pour bissectrice d'un angle
[PDF] méthode pour calculer limites fonctions trigonométriques
[PDF] Méthode pour commentaire Bac !!!
[PDF] methode pour déterminer la vitesse de déplacement des plaques tectoniques
[PDF] méthode pour écrire un slam
