Algorithme, exercice sur médiane
Bonjour, voila j'ai un petit problème sur un algorithme les idées ne me viennent pas, pourriez vous m'aider j'ai un Control demain ?
Le sujet :
On considère un ensemble un ensemble d'objet S, sous-ensemble d'un univers U muni d'une relation d'ordre total <=. Soit n = [ |S| / 2], ou |S| est la cardinalité de S. La médiane de S est la valeur intermédiaire de S, c-a-d l'élément x de S qui est plus petit à exactement n éléments de S.
Question : Ecrire une algo abstrait MED qui permet de trouver la médiane de S. L'algo doit tourner en O(n*logn) dans le pire des cas et doit être en O(1) en espace. Evidemment, trier une représentation de S n'amène pas a la bonne solution.
Merci d'avance .