Complexité de l'algorithme de Tri FusionRésolu

Question

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

acx01b · Answer

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+

cs_ousin · Answer

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

acx01b · Answer

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é

cs_ousin · Answer

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

acx01b · Answer

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é"

acx01b · Answer

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

cs_ousin · Answer

Merci beaucoup je vois bien

ousin

Complexité de l'algorithme de Tri Fusion

7 réponses

Votre réponse

Discussions similaires