Trouver la médiane d'un tableau [Résolu]

[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]

Envoyé par mat1554

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]

Envoyé par souviron34

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.

[souviron34]

Envoyé par Celelibi

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²).

euh... Non, on explore toujours au max N valeurs... Que ce soit sur les valeurs ou les inidices.

D'ailleurs , qu'est-ce qu'une médiane ? C'est bien une valeur, non ??

Le tri t'oblige à raisonner sur les indices..

Sachant que la moyenne est M, on explore une fois et on compte combien de valeurs sont en dessus (ou en dessous). Si le nombre considéré est > N/2, c'est que la médiane est entre la moyenne et la valeur min. (valeur max) .

Donc on réduit l'intervalle en 2, et on itère..

A chaque fois on ne parcours que N, et à chaque fois on réduit l'intervalle par 2.

[Celelibi]

Envoyé par souviron34

euh... Non, on explore toujours au max N valeurs... Que ce soit sur les valeurs ou les inidices.

Les valeurs sont potentiellement non bornées si on utilise des entiers de précision arbitraire.
Si ton tableau contient 3 valeurs {0, 2^4000, 1+2^4000}, ça serait dommage de faire dans les 4000 itérations.

Dans tous les cas, je m'oppose à l'utilisation du même N.

Envoyé par souviron34

D'ailleurs , qu'est-ce qu'une médiane ? C'est bien une valeur, non ??

Dans le cas général, rien ne dit qu'on sache faire autre chose qu'une comparaison entre les éléments dont on cherche la médiane. Mais je chipottes parce qu'on lui a déjà demandé la moyenne. :p


Sinon, je viens de lire la page wikipedia... Visiblement, l'algo que j'ai esquissé ci-dessus s'appelle le quickselect.

[mat1554]

J'ai pas encore eu le temps de regarder. Mais en pouvant déplacer certaine valeur, sans que se soit toutes les valeurs, ça sera a première vu plus simple.

Et oui, je crois que ça serait un genre de QuickSelect. En gros je parcours mon tableau au maximum N fois pour trouver ma médiane. Tous en faisant le total, et une fois la médiane trouver, je ne fais que continuer a calculer le total.

Cependant J'avoue avoir toujours eux du mal a calculer le temps des Algo, O(n), O(n²),etc xD

Je sais qu'un (for,while) c'est O(n), mais pour le reste ^^

[souviron34]

Envoyé par Celelibi

Les valeurs sont potentiellement non bornées si on utilise des entiers de précision arbitraire.
Si ton tableau contient 3 valeurs {0, 2^4000, 1+2^4000}, ça serait dommage de faire dans les 4000 itérations.

Tu n'as pas compris.....

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Valeur moyenne 2^4000

Delta = N/2
Ref = moyenne

Faire jusqu'à ce que Delta <= 1

   pour i = 0 jusqu'à N
       si val(i) <= Ref
           m = m + 1
       fin si
   fin pour

   si m < N/2
      Delta = (max - Ref)/2
      Ref = Ref + Delta
   sinon
      Delta = (Ref-min)/2
      Ref = Ref - Delta
   fin si

fin faire

je ne vois pas où apparaîtraient les valeurs dans les indices de boucles.. On fait bien log(N) boucles contenant une boucle sur N.. Donc N log(N)

[mat1554]

Question, dans ton Algorithme. Ta valeur moyenne, vient d'ou.

Car dans mon cas je ne connais pas la moyenne.

En gros l'entête de mon algo peu ressembler a ceci.
DeterminerMoyenne(int[] tableau, out Moyenne, out PlusPetitMoyenne)

[souviron34]

Envoyé par mat1554

Question, dans ton Algorithme. Ta valeur moyenne, vient d'ou.

De là où tu l'as déterminée..

Ici je la prend comme une entrée... comme le min et le max..

[mat1554]

Ah OK, dans mon cas, je voyais dans optique ou on calcul tous dans le même module. Vu que je parcours déjà mon tableau N/2 assuré pour déterminer mon Médian

[souviron34]

Envoyé par mat1554

Vu que je parcours déjà mon tableau N/2 assuré pour déterminer mon Médian

???

Comme on a dit, déterminer la moyenne, le min et le max en même temps se fait en O(N)

Si tu as besoin d'une fonction CalculeMedian avec juste en paramètres, tableau, et N ça marche aussi..

Par contre, comme j'ai mis au dessus, je ne vois pas coment tu peux faire en ne parcourant que N/2...

[mat1554]

Oui pour la médian N/2 au mieux.

Cependant, ou fois que j'ai trouvé la Median, je n'est plus besoin de «re boucler» sur mon tableau pour le reste. Je calcul seulement le reste du tableau.


Mais la je suis intriguer sur une chose je dois déterminer le nombre de valeurs inférieures .

Si j'ai [1,1,1,1,1,3] , ma moyenne est de 1.3.

Cependant, mon 1 se répète, donc je reste perplexe, est-ce que je dois compté les valeurs qui se répète ou pas...

[Celelibi]

Envoyé par souviron34

Tu n'as pas compris.....

Code :

je ne vois pas où apparaîtraient les valeurs dans les indices de boucles.. On fait bien log(N) boucles contenant une boucle sur N.. Donc N log(N)

Si si, j'ai très bien compris. Tu fais une dichotomie sur les valeurs du tableau jusqu'à en trouver une qui sépare correctement l'ensemble en deux parties égales. Et c'est ta boucle "jusqu'à ce que" qui va faire un nombre de tour dépendant de l'amplitude des valeurs du tableau (dépendance logarithmique, mais dépendance quand-même).

Par contre, l'algorithme que tu as donné... Il est plein d'erreurs.
1) Quelle est la dimension (unité / type) de Delta ? Sa première affectation lui donnerait la dimension d'un indice, les autres lui donneraient la dimension d'une valeur. Admettons que l'initialisation était plutôt Delta = max - min.
2) Le test Delta <= 1 n'est valable que si les valeurs du tableau sont des entiers et pas des rationnels. Mais admettons qu'on n'a à faire qu'à des entiers.
3) max et min ne sont jamais affectés, j'imagine qu'il s'agit de la valeur max et min du tableau.
4) Chose amusante : sous l'assertion précédente, cet algo ne termine pas sur la liste suivante : [0, 1500, 3998, 3999, 4000]. La valeur de Ref va osciller de part et d'autre de 1500 (qui est la valeur juste précédant la médiane).
(Et quand il termine, cet algo a la fâcheuse tendance à retourner la valeur précédant la médiane.)
J'imagine que la supposition 3) étaient fausses et que ce sont en fait les bornes de l'interval à explorer et qu'il faut les mettre à jour à chaque itération.

(5) Adapter cet algo pour gérer les multiplicités et les cas où la médiane n'est ni entière ni un élément du tableau n'est pas immédiat ou pas élégant.)

Et donc, pour finir de te convaincre que le nombre d'itérations dépend de la valeur des données, voilà une implémentation en python (à peu près débugguée, il ne gère pas le point 5) sus-cité) de ton algo avec un comptage des itérations.

Code python :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#!/usr/bin/python
 
 
tab = [0, 1, 2, 3, 2**4000]
n = len(tab)
mi = min(tab)
ma = max(tab)
moyenne = sum(tab) / n
 
delta = ma - mi
ref = moyenne
 
cpt = 0
while delta > 0:
        m = 0
        l = 0
        for i in range(0, n):
                if (tab[i] < ref):
                        m = m + 1
                elif (tab[i] > ref):
                        l = l + 1
 
        if (m < l):
                delta = (ma - ref) / 2
                mi = ref
                ref = ref + delta
        elif (m > l):
                delta = (ref - mi) / 2
                ma = ref
                ref = ref - delta
        else:
                delta = 0
 
        cpt = cpt + 1
 
print "mediane " + str(ref)
print str(cpt) + " iterations"

Résultat :

Code :

1
2
mediane 2
3998 iterations

Et on modifie l'exposant de la dernière valeur du tableau, le nombre d'itération varie d'autant (à plus ou moins quelques unités).

[Celelibi]

Envoyé par mat1554

Oui pour la médian N/2 au mieux.

Vérifier qu'une valeur est une médiane demande au minimum de parcourir tout le tableau au moins une fois. Il est donc impossible (même dans le meilleur des cas) de calculer la médiane en ne parcourant que la moitié du tableau.

Envoyé par mat1554

Mais la je suis intriguer sur une chose je dois déterminer le nombre de valeurs inférieures .

Si j'ai [1,1,1,1,1,3] , ma moyenne est de 1.3.

Cependant, mon 1 se répète, donc je reste perplexe, est-ce que je dois compté les valeurs qui se répète ou pas...

Dans le cas que tu as cité, ta médiane est 1. Cela est certainement expliqué sur wikipedia.

[mat1554]

N/2 ne fonctionne pas ? N étant le nombre d'élements du tableau.

Si tableau est impair (3 valeurs)
--> 1,2,3
N/2 = 1.5, donc 1.

Donc j'ai 1 valeur PP que ma médiane.D'ou mon au mieux N/2. Mais j'ai peut-être tord, je suis encore en test ^^

------------

Sinon, dans mon exemple oui ma médiane est de 1. Mais je dois trouvé la moyenne, ici 1.3, et le nombre de valeur inférieur a ma moyenne.

Mais bon, je vais le faire comme je le pense, et qui est normal, donc ça serait 5 valeurs inférieur à la moyenne.

[souviron34]

Envoyé par Celelibi

Si si, j'ai très bien compris. Tu fais une dichotomie sur les valeurs du tableau jusqu'à en trouver une qui sépare correctement l'ensemble en deux parties égales. Et c'est ta boucle "jusqu'à ce que" qui va faire un nombre de tour dépendant de l'amplitude des valeurs du tableau (dépendance logarithmique, mais dépendance quand-même).

NON

Je me suis légèrement trompé sur la boucle (tard et autre chose en tête), et j'ai effectivement oublié de remettre à jour min et max.. mais je remet ici le code..

• Calcul de la moyenne et du min/max
  
  
  Code :

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  min = MAX_REEL
  max = -MAX_REEL
  moy = 0.0
  
  pour i = 1 jusqu'à i = N
  
     moy = moy + val(i)
  
     si val(i) < min
         min = val(i)
     fin si
  
     si val(i) > max
         max = val(i)
      fin si
  
  fin pour
  
  moy = moy/N

• Calcul de la médiane
  
  
  Code :

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  milieu = N/2
  Diff = milieu
  Ref = moy
  
  Faire jusqu'à ce que Diff <= 1
  
     m = 0
     pour i = 1 jusqu'à N
         si val(i) <= Ref
             m = m + 1
         fin si
     fin pour
  
     si m < milieu
        Diff = milieu - m
        Delta = (max - Ref)/2
        min = Ref
        Ref = Ref + Delta
     sinon
        Diff = m - milieu
        Delta = (Ref-min)/2
        max = Ref
        Ref = Ref - Delta
     fin si
  
  fin faire

C'est bien INDEPENDANT des valeurs, et c'est bien en O(N) (moyenne) et log(N)*N (médiane).