[algo / info fonda] tri par tas et complexité

Discutez d'informatique ici !
ghghgh
Membre Relatif
Messages: 305
Enregistré le: 04 Aoû 2006, 17:20

[algo / info fonda] tri par tas et complexité

par ghghgh » 20 Juil 2010, 21:48

Bonsoir,
Je suis en train de réfléchir sur quelques exercices, et en voici deux sur lesquels je butte :

1. Montrer que le temps d'exécution du tri par tas dans le cas le plus défavorable est .

2. Montrer que, quand tous les éléments sont distincts, le temps d'exécution optimal du tri par tas est .

Comment rédigeriez-vous ça proprement ? de manière assez formelle ?

Si nécessaire, je puis fournir un pseudo-code du tri par tas.

Merci d'avance, et bonne soirée !



ghghgh
Membre Relatif
Messages: 305
Enregistré le: 04 Aoû 2006, 17:20

par ghghgh » 20 Juil 2010, 22:02

Précision : je souhaiterais une démonstration pour ce cas particulier.
Sinon, on peut toujours passer par le modèle de l'arbre de décision.
Et montrer : Tout algorithme de tri par comparaison exige comparaisons dans le cas le plus défavorable.
Démonstration faite avec des inégalités sur la hauteur de l'arbre de décision.

Puis, pour la deuxième question, montrer le corollaire : Le tri par tas et le tri par fusion sont des tris par comparaison asymptotiquement optimaux.

En montrant que les majorants sont en O(n lg n), ce qui correspond au minorant du cas le plus défavorable.

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 2 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite