Complexité de l'algorithme de Tri Fusion

Réponse acceptée !
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+