Etude de tri fusion

Fermé
zmandar - 17 nov. 2010 à 19:58
Bonjour,
svp aide moi à ce tp :


Étude plus approfondie du tri par fusion
exercice 1:Calculs des coûts minimaux et maximaux
En cours il a été établi que le nombre cn de comparaisons dans le tri par fusion d'un tableau de taille
n est donné par

c1 = 0
cn = c[n/2]+c[n/2]+cn' n>=2
avec les notations
[x] = plus grand entier inférieur ou égal à x ( plancher  de x, ou encore partie entière de x) ;

[x] = plus petit entier supérieur ou égal à x ( plafond  de x) ;
cn' :est le coût de la fusion de deux tranches de longueur totale égale à n.
On sait que ce dernier coût est compris entre [n/2] et n ? 1.

[n/2]<=cn'<= n ? 1
On en déduit que cn sera compris entre deux suites cminn et cmaxn dénies par les mêmes équations
que ci-dessus avec
cn' = [n/2] pour cminn ;

et cn' = n ? 1 pour cmaxn.
Exercice 2: Écrivez une fonction récursive pour calculer cminn. Utilisez-la pour calculer cminn
pour n compris entre 2 et 512. Sauvegardez ces valeurs dans un chier.
Même chose avec cmaxn.
exercices 3: produiser un graphique superposant les courbes cmin, cmax et cn pour le tri fusion de tableau quelconque .qu' en dites vous ??
exercices 4:
comparez cmax et nlog2(n)-n . en particulier ,faites une représentation graphique de cmax nlog2(n)+n.