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

[ghghgh]

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]

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.