Discussion :

[algoCC]

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 .

[kwariz]

Salut,

En fait tu cherches un algorithme qui te donne la nième plus petite valeur. Il y a pas mal de littérature sur ça. Par contre je ne comprends pas ta remarque sur le tri. Je suppose que si tu tries et que tu prends la nième valeur le tour est joué en O(n.lg n) temps mais en O(n) espace et là est le problème. Donc il y a une solution : l'algo de la médiane des médianes, il est en O(n) temps et O(1) espace : Linear general selection algorithm - Median of Medians algorithm
et plus généralement une recherche avec "median of medians algorithm" sur google pour avoir des liens.

[algoCC]

On pourrait penser a faire un tri fusion ou autre au debut pour que l'algorithme soit trié et en nlogn , mais vu que l'ensemble d'objet est muni d'une relation d'ordre total <= , je pense que c'est déjà trié, du style :

S = {1,2,4,4,7,8}

[kwariz]

Si tu dois le faire en O(1) espace, tu ne peux pas garder tous les éléments en mémoire car dans ce cas ton algo serait en O(n) espace minimum.
Si tu as le droit de le faire en O(n) espace avec un espace supplémentaire en O(1) alors n'importe quel tri en O(n.lg n) temps et O(n) espace convient, l'accès à la médiane étant ensuite en temps constant.
Rien n'indique que ton S soit trié au départ, c'est U qui est muni d'un ordre total, S n'en est qu'un sous (multi)ensemble.

[algoCC]

Merci beaucoup, je vais essayer de comprendre un peu plus