Complexité de l'algorithme de Tri Fusion [Résolu]

Signaler
Messages postés
9
Date d'inscription
vendredi 11 mars 2005
Statut
Membre
Dernière intervention
9 février 2008
-
Messages postés
9
Date d'inscription
vendredi 11 mars 2005
Statut
Membre
Dernière intervention
9 février 2008
-
Salut tout le monde, je voudrais de l'aide pour demontrer mathematiquement en urilisant la resolution des reccurences que la complexité du Tri Fusion est: T(n) = O(nlogn); Merci

ousin
A voir également:

7 réponses

Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
4
salut

le logn (log en base 2 a prori!) c'est le nombre de fois que tu découpes ta liste à trier en 2:

- d'abord tu découpes en 2 morceaux
- puis tu découpes chaque morceau en 2 morceaux ce qui fait 2^2 morceaux
- puis tu découpes chaque morceau en 2 morceaux ce qui fait 2^3 morceaux
- puis tu découpes chaque morceau en 2 morceaux ce qui fait 2^4 morceaux
- ...
- puis tu découpes chaque morceau en 2 morceaux ce qui fait 2^(logn) morceaux
--> mais là t'as des morceaux de taille 1 ou 0 (qui sont faciles à trier)
puis tu dépiles la chaine récursive: en concatènant les morceaux 2 à 2
- de tes 2^(logn) morceaux de taile 1 tu fais 2^(logn - 1) morceaux de taille 2
- de tes 2^(logn - 1) morceaux de taile 2 tu fais 2^(logn - 2) morceaux de taille 2^2
- de tes 2^(logn - 2) morceaux de taile 2^2 tu de fais 2^(logn - 1) morceaux de taille 2^3
- ...
- avec tes 4 morceaux de taile n/4 tu fais 2 morceaux de taille n/2
- avec tes 2 morceaux de taile n/2 tu fais 1 morceau de taille n

si on considére que empiler les appels de fonctions ne coûte rien, on voit que tout le travail est fait au moment de dépiler: à chaque fois on doit traiter les n éléments séparés dans 2^i morceaux pour les rassembler en morceaux 2 fois plus gros, donc obtenir les n éléments séparés dans 2^(i-1) morceaux, ce qui coùte quelque chose de proportionnel au nombre d'éléments: n

et ça logn fois, d'où finalement le nlogn

j'espère que ma réponse te vas, a+
Messages postés
9
Date d'inscription
vendredi 11 mars 2005
Statut
Membre
Dernière intervention
9 février 2008

Merci, je comprend mieux mais y a une phrase qui me derrange un peu: puis    tu découpes chaque morceau en 2 morceaux ce qui fait 2^(logn) morceaux;

est-ce une egalité si oui pourquoi? merci

ousin
Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
4
salut

disons que j'ai un tableau avec 32 éléments
log en base 2 de 32 5 (car 2^5 32)
je découpe une fois en 2: j'ai 2 morceaux de 16 éléments
je découpe encore une fois en 2: j'ai 2^2 morceaux de 8 éléments
je découpe encore une fois en 2: j'ai 2^3 morceaux de 4 éléments
je découpe encore une fois en 2: j'ai 2^4 morceaux de 2 éléments
je découpe encore une fois en 2: j'ai 2^5 morceaux de 1 éléments
mes morceaux de 1 élément sont tous faciles à trier :)
2^5 2^(log 32) 32 --> j'ai découpé logn fois mes n morceaux pour obtenir
2^(logn) = n morceaux de taille 1

puis je concatène logn fois mes morceaux 2 à 2 pour obtenir mon tableau complétement trié
Messages postés
9
Date d'inscription
vendredi 11 mars 2005
Statut
Membre
Dernière intervention
9 février 2008

Oui, merci! je comprend mais là c dans le cas où n est pair mais de maniere generale a-ton l'egalité? Je crois que le nombre de morceaux est inferieur ou egal  à logn prenons par exemple n=3

ousin
Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
4
si n = 3 tu découpes en 2 ça te fait un morceau à 2 éléments, puis un morceau à 1 éléments, puis tu redécoupes encore en 2, ça te fait 3 morceaux à 1 élément et 1 morceau à un élément et là trier chaque morceau est trivial

de toute façon quand on cherche la complexité on différencie pas logn-1, log(n-1), 2*n^5 et 45*n^3, on cherche plutôt un "odre de complexité"
Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
4
pardon j'ai mal écrit:

si n = 3 tu découpes en 2 ça te fait un morceau à 2 éléments et un morceau à 1 éléments, puis tu redécoupes encore en 2, ça te fait 3 morceaux à 1 élément et 1 morceau à zéro élément et là trier chaque morceau est trivial
Messages postés
9
Date d'inscription
vendredi 11 mars 2005
Statut
Membre
Dernière intervention
9 février 2008

Merci beaucoup je vois bien

ousin