Discussion :

[mat1554]

Bonjour à tous,
Dans le cadre de mon cours, le prof nous a donnée un petite exercices ou on doit trouver la médiane dans un tableau de X élements, ou certains éléments peuvent se répéter.

Normalement, ça serait facile de le trouver je commencerais par trier mon tableau et je retourne élément N/2 (tableau impair) ou encore la moyenne de N/2 & N/2+1 (tableau impair). Cependant, le prof nous donne une contrainte qui me fait bloquer entièrement, il refuse qu'on tri le tableau.

En gros, mon algorithme doit :

• Calculer et retourner la médiane d'un tableau sans le trier.
• Déterminer la moyenne du tableau
• Déterminer le nombre d’élément plus petit que la moyenne.

Ensuite je vais devoir déterminer :

• Temps d’exécution dans le pire cas
• Temps d'exécution dans le meilleur cas.

En cherchant sur internet, je suis tombé sur certaine site ou on parlais de calcul linéaire,déterminisme,etc. Mais j'ai rien trouvé qui me donnée une explication claire si je peu le dire ainsi. Surtout que dans la plus part des cas, les données du tableau était permuter.


En faisant quelques tests j'ai sortis 5,6 version d'Algo différent que j'ai tester en le transposant en C#, cependant je me retrouver toujours que dans certains cas de tests j'ai une erreur.

Merci d'avance !

[Celelibi]

Moyenne et nombre de valeurs inférieurs à la moyenne, c'est trivial et ça se fait en O(n).
Pour la médiane, je ne vois rien de mieux qu'un tri, donc la complexité minimale serait O(n log n).

S'il refuse que tu trie ce tableau et que tu n'as aucune contrainte d'utilisation de mémoire, crée une copie triée du tableau.

Et je pense que tous les algos en O(n log n) que tu peux trouver pour calculer la médiane seront des algos de tri plus ou moins cachés. Et tous les algos auxquels je pense actuellement sont en O(n²). Mais je pense que t'as du trouver les mêmes.

[souviron34]

euh...


Je peux voir l'intérêt d'un tri, mais ce n'est d'aucune manière nécessaire..

Reprenez la définition :

http://fr.wikipedia.org/wiki/M%C3%A9...tatistiques%29

une médiane d'un ensemble de valeurs ... est une valeur m telle que le nombre de valeurs de l'ensemble supérieures ou égales à m est égal au nombre de valeurs inférieures ou égales à m.

Il suffit donc de faire un comptage...

Et c'est en O(N logN)...

[mat1554]

@Celelibi
Oui pour la moyenne et le nombre de chiffre en bas de la moyenne ça va sans aucun problème. Mon problèmes majeur était(est) vraiment la médiane.

Mais puisqu'il disait «ne pas trier les valeurs», je lui est envoyé un message pour justement savoir si je pouvais faire une copie du tableau. J'attends ça réponse et si telle est le cas, ça sera parfait.

Dans situation contraire, c'est très intriguant...

@souviron34
Oui, l'optique de l'option de comptage peut-être une idée, bien qu'il faut avouer que question optimisation c'est pas tous à fait ça. Mais si je n'ai pas le droit d'avoir un second tableau, je n'aurais pas trop le choix.

En tous cas, merci de votre aide, et je vous donnerais des nouvelle dès que j'en aurais eu de prof et que j'aurais quelques chose

Edit :
Réponse du prof : «Justement, le défi est de ne pas trier (au moins, pas totalement)». Donc, rendu là il suffit de gardé une des optiques qui m'avait passé par la tête.

Trier les valeurs jusqu'à ce que j'ai N/2 nombre plus petit. Bref, un mélange des 2 solutions, tri & comptage

[souviron34]

Oui, l'optique de l'option de comptage peut-être une idée, bien qu'il faut avouer que question optimisation c'est pas tous à fait ça. Mais si je n'ai pas le droit d'avoir un second tableau, je n'aurais pas trop le choix.

euh...

Tu calcules la moyenne. O(N)

Tu parcoures la table en comptant avant et après la moyenne O(N)

Tu procèdes ensuite par dichotomie à partir de la moyenne : N/2*log(n)

[mat1554]

Enfaite la moyenne et le nombre de chiffre en bas de la moyenne ça va sans aucun problème. C'était vraiment la médiane mon problème.

[Celelibi]

euh...

Tu calcules la moyenne. O(N)

Tu parcoures la table en comptant avant et après la moyenne O(N)

Tu procèdes ensuite par dichotomie à partir de la moyenne : N/2*log(n)

C'est une méthode à laquelle j'ai pensé, mais le problème c'est que tu es obligé de raisonner sur les valeurs du tableaux et non plus uniquement sur la taille du tableau.
Cet algo n'est pas en O(N log N), mais en O(N log M), avec M l'intervalle des valeurs du tableau, ce qui est tout à fait différent et potentiellement pire qu'un algo naïf en O(N²).

Ce que je peux proposer comme algo en O(N log N) c'est un quicksort où on ne trie que la partie où se trouve la médiane et où on s'arrête dès qu'on a trouvé pivot qui correspond à la médiane.
D'ailleurs, vu qu'on ne trie que la partie qui nous intéresse, je crois que cet algo est en O(N) en moyenne et O(N²) au pire. À vérifier tout de même.