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

[pseudocode]

Envoyé par mat1554

Ouep, mais bon en gros le prof disait de pas toucher au valeur, en parlant de tri. Mais je crois que retirer reviens a touché au valeur aussi ^^.

Tu peux swapper les min/max en fin de liste, et itérer sur le tronçon qui reste.

Code java :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int[] list = {12, 5, 6, 89, 5, 2390, 1};
int length = list.length;
 
while (length>2) {
	int index_min = indexOfMin(list, 0, length); 
	swap(list, index_min, length-1);
	length--;
 
	int index_max = indexOfMax(list, 0, length); 
	swap(list, index_max, length-1);
	length--;
}
 
if (length==2) System.out.println((list[0]+list[1])*0.5);
if (length==1) System.out.println(list[0]);

Ou alors, comme le dit prgasp77, utiliser une liste des index à "oublier".

[souviron34]

Envoyé par pseudocode

Algo bête et méchant:

En fait, je pensais (je vérfierais demain) faire la même idée que j'ai expoée plus haut (qui donne une seule itération pour tout sauf le premier cas (4) et le cas de puissance, qui donne x fois N, x étant la puissance), mais en prenant une valeur relative (qui correspond un peu à l'idée de ton algo

Je vous tiens au courant demain..

[Celelibi]

Ce que je peux te proposer comme algo bête en O(N²), si tu ne veux pas du tout toucher au tableau, c'est :
Prendre une valeur de référence, et parcourir le tableau pour à la fois compter le nombre de valeurs inférieures à la référence, et aussi trouver la plus petite valeur strictement supérieure à la valeur de référence (qui serait la suivante si le tableau était trié).
Et de recommencer avec la valeur suivante comme valeur de référence tant que le comptage des valeurs inférieures à la référence n'est pas suffisant.

Sous forme de pseudocode, ça donne ça :

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
28
29
30
31
32
33
34
35
36
37
38
39
ref = min(tab)

faire
    inf = 0
    mult = 0
    next = tab(1)
    pour I de 1 à N faire
        si tab(I) < ref alors
            inf = inf + 1
        sinon si tab(I) == ref alors
            mult = mult + 1
        sinon si tab(I) > ref et tab(I) < next alors
            next = tab(I)
        fin si
    fin pour

    si N est impaire alors
        si inf == (N-1)/2 alors
            // Cas classique N impaire
            retourner ref
        sinon si inf + mult >= (N-1)/2 alors
            // Cas où les multiplicités incluent la médiane [0, 1, 1, 2, 3]
            retourner ref
        fin si
    sinon
        // N est paire
        si  inf == (N/2)-1 alors
            // Cas classique N paire
            retourner (ref + next) / 2.0
        sinon si inf + mult == N/2 alors
            // Cas où les multiplicités "touchent" la médiane [1, 1, 2, 3]
            retourner (ref + next) / 2.0
        sinon si inf + mult > N/2 alors
            // Cas où les multiplicités incluent la médiane [1, 1, 1, 3]
            retourner ref
        fin si
    fin si

    ref = next

C'est une adaptation du tri par sélection. Sauf qu'on ne touche pas au tableau.
(Y'a beaucoup de if pour gérer les cas spéciaux avec les multiplicité, mais c'est pas complique.)

[mat1554]

Bon, j'ai fini pas faire 2 version fonctionnel. Je vous donne la version C#.

Avec un demi-trie (la moyenne n'est pas ajouté. Donc le plusPetit que la moyenne ne fonctionne pas plus )

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
      public double determinerMedianeV8(int[] tab, out double moyenne, out int plusPetit)
        {
            int Indice = 0, Total = 0, ppMed = 0;
            int Tempo = 0;
            double Med = 0;
            bool isPair = false;

            if (NbrElement % 2 == 0)
            {
                ppMed = NbrElement / 2;
                isPair = true;
            }
            else
            {
                ppMed = (NbrElement-1) / 2;
            }

            while (Indice <= ppMed)
            {
                int Compare = Indice+1;
                while (Compare < NbrElement)
                {
                    if (tab[Compare] < tab[Indice])
                    {
                        Tempo = tab[Compare];
                        tab[Compare] = tab[Indice];
                        tab[Indice] = Tempo;
                    }
                    Compare++;
                }
                Indice++;
            }

            if (isPair)
            {
                Med = (double)(tab[ppMed] + tab[ppMed - 1]) / 2;
            }
            else
            {
                Med = (double)tab[ppMed];
            }
         
            moyenne = Total;
            plusPetit = NbrElement / 2;
            return Med;

        }

Sans trier, simplement en calculant (il manque le calcul du nombre de valeur inf à la moyenne)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
public double determinerMedianeV9(int[] tab, out double moyenne, out int plusPetit)
        {
            int Indice = 0, nPP = 0, Tempo = -1, Total = 0;
            double Med = 0;
            int MedPos = NbrElement/2, Comparant = 0;

            bool isPair = false;
            if (NbrElement%2 == 0)
            {
                isPair = true;
            }

            while (Indice < NbrElement)
            {
                Total += tab[Indice];
                Comparant = 0; //  Indice + 1;
	            while (Comparant < NbrElement)
                {
                    if (tab[Comparant] < tab[Indice])
                    {
                        nPP++;
                    }
                    Comparant++;
                }

                if (!isPair)
                {
                    if (nPP == MedPos)
                    {
                        Med = tab[Indice];
                    }
                }
                else
                {
                    if ((nPP == MedPos) && (Tempo == -1))
                    {
                        Tempo = tab[Indice];
                    }
                    else if ((nPP == MedPos-1) && (Tempo == -1))
                    {
                        Tempo = tab[Indice];
                    }
                    else if ((nPP == MedPos) && (Tempo > -1))
                    {
                        Med = (double) (Tempo+tab[Indice]) / 2;
                    }
                    else if ((nPP == MedPos-1) && (Tempo > -1))
                    {
                        Med = (double) (Tempo+tab[Indice]) / 2;
                    }   
                }
                nPP = 0;
                Indice++;
            }
            moyenne = (double) Total / NbrElement;


            /*
             * Seule bogue ici
             */
            if (isPair)
            {
                plusPetit = NbrElement / 2;     // A vérifier
            }
            else if (NbrElement == 1)
            {
                plusPetit = 0;
            }
            else
            {
                plusPetit = (NbrElement+1) / 2;
            }
            return Med;
        }
        
    }

Un peu basé sur tous ce que vous avez dis xD

[Celelibi]

Ton premier algo est un vrai tri par sélection. Sauf que tu t'arrêtes au milieu. Il a l'avantage de pas avoir de cas particulier pour les mutiplicités. Mais a l'inconvénient d'être en O(N^2) et de modifier le tableau.


Par contre j'ai pas compris ton deuxième algo.

[souviron34]

Je reviendrais vers vous cette am, mais je crois que j'ai un algo en O(N log(log(M)) dans le pire des cas.... (sans tri, et qui pourrait se faire "in place").

[mat1554]

Envoyé par Celelibi

Ton premier algo est un vrai tri par sélection. Sauf que tu t'arrêtes au milieu. Il a l'avantage de pas avoir de cas particulier pour les mutiplicités. Mais a l'inconvénient d'être en O(N^2) et de modifier le tableau.


Par contre j'ai pas compris ton deuxième algo.

Oui, en gros je tri jusqu’à valeur, donc ça limite ce que je le prof disait. «Le défi est de ne pas trie (du moins au complet)»

O(n/2) et o(n) sont bien les seules que j'arrive a calculer ^^ Comme mon second vu que je parcours 2 fois, je crois que ça serait O(n²) ? Mais vraiment pas sûr.

Cependant, dans la version avec tri, il me manque le calcul de la moyenne et du nombre de valeur plus petit que la moyenne.

Et dans la seconde, du nombre de valeur plus petit que la moyenne.

Donc, ça va encore modifié la complicité de O.

[souviron34]

Envoyé par souviron34

Je reviendrais vers vous cette am, mais je crois que j'ai un algo en O(N log(log(M)) dans le pire des cas.... (sans tri, et qui pourrait se faire "in place").

En fait, c'est même en O(N log^c M), c >= 2.... (le ^ est pour le logarithme itéré).

Donc potentiellement O(N)...

[Celelibi]

Bien, montre-nous ton algo.
Au pire, on trollera sur la complexité.

[mat1554]

Envoyé par Celelibi

Par contre j'ai pas compris ton deuxième algo.

Oups j'avais sauté cette phrase en première lecture xD

Enfaite, je prends chaque Indice du tableau, puis je compte le nombre de valeur inférieur.

Ensuite, celui qui a NbrElement/2 élement inférieur. Bien ça me donne mon Median.

Cependant, dans le cas d'un tableau de NbrElement pair, j'ai besoin de 2 nombre pour déterminer mon médiane sois : N/2 et N/2+1. Je cherche donc c'est 2 résultat.

[prgasp77]

Envoyé par mat1554

Le défi est de ne pas trie (du moins au complet)

Mais raison de plus pour un quickselect. On ne trie que ce qu'il faut (c'est à dire que l'on positionne quelques éléments, et c'est tout). Pourquoi tourner autour du pot ?

[souviron34]

Envoyé par Celelibi

Bien, montre-nous ton algo.
Au pire, on trollera sur la complexité.

En fait, j'en ai 2..

Un comme dérivé du premier que j'avais indiqué, qui est en O(N logc M), et l'autre linéaire, en O(N), ressemblant furieusement à ce qu'on peut lire dans les Selection algorithm à la rubrique Linear minimum/maximum algorithms.

Je les posterrais tout à l'heure..

[souviron34]

OK, alors voilà..

• D'abord l'algo en O(N logc M)
  
  La remarque de base est que pour classer des points, on a juste besoin d'une fonction croissante... Le log est une fonction croissante.. Là je présente avec un log simple, mais on peut augmenter en doublant, triplant, etc (mais ça fait des expression plus complquées).
  
  La seconde remarque est que pour ne pas avoir de problèmes avec les logs, il faut que x soit > 0. Donc, dans le cas du log simple on se ramène à [1, +infini], pour le log double à [10, +infini], etc etc...
  
  Enfin, ça marche par dichotomie comme indiqué dans un de mes premiers posts..
  
  Note1 : comme je n'ai pas de 64 bits mais 32, j'ai testé avec 2^1000 et non 2^4000 ;
  
  Note2 : il reste un cas à problème : les cas dégénérés dans le cas impair.. J'ai la femme .
  
  
  Code C :

  
  Resultat :
  
  

  Moyenne 0.584856 et 3 iterations pour mediane
  Tableau 1 mediane 2
  
  Moyenne 0.415836 et 1 iterations pour mediane
  Tableau 2 mediane 2
  
  Moyenne 0.400515 et 1 iterations pour mediane
  Tableau 3 mediane 2
  
  Moyenne 0.345053 et 1 iterations pour mediane
  Tableau 4 mediane 1.5
  
  Moyenne 60.482 et 8 iterations pour mediane
  Tableau 5 mediane 2
  
  Moyenne 0.0752575 et 1 iterations pour mediane
  Tableau 6 mediane 0

  
  
• Algo linéaire O(N) : aucun cas particulier.
  
  Le pirncipe de base est de trouver la moyenne, puis le point le plus proche dans le tableau (par valeur inférieure), puis à chaque fois qu'on explore de trouver les valeurs les plus proches, la plus proche superieure et la plus proche inférieure.
  
  Là si on n'a pas le résultat, on fait une sorte de dichotomie, mais simplement entre l'ancienne valeur et l'une ou l'autre.. On n'a donc que des valeurs du tableau initial... Et une convergence que je ne saurais pas analyser, mais il me semble en O(1) : on cherche juste parmi les 2 points voisins..
  
  Donc normalement on devrait avoir au plus un facteur constant de 4 pour les cas impairs et 6 pour les cas pairs...
  
  
  Code C :

  
  
  Resultat :
  
  

  Moyenne 8 et 2 iterations pour mediane
  Tableau 1 mediane 2
  
  Moyenne 2 et 1 iterations pour mediane
  Tableau 2 mediane 2
  
  Moyenne 2 et 1 iterations pour mediane
  Tableau 3 mediane 2
  
  Moyenne 1.5 et 1 iterations pour mediane
  Tableau 4 mediane 1.5
  
  Moyenne 2.14302e+300 et 2 iterations pour mediane
  Tableau 5 mediane 2
  
  Moyenne 0.25 et 1 iterations pour mediane
  Tableau 6 mediane 0

  
  

[mat1554]

Envoyé par prgasp77

Mais raison de plus pour un quickselect. On ne trie que ce qu'il faut (c'est à dire que l'on positionne quelques éléments, et c'est tout). Pourquoi tourner autour du pot ?

Enfaite, il laisse possibilité de pas trier au complet. Mais si on peut y arriver sans rien trier du tous, c'est encore mieux selon moi

Mais mes 2 algo fonctionnelle sont citer un peu plus haut.

[pseudocode]

Envoyé par souviron34

[*]Algo linéaire O(N) : aucun cas particulier.

Le pirncipe de base est de trouver la moyenne, puis le point le plus proche dans le tableau (par valeur inférieure), puis à chaque fois qu'on explore de trouver les valeurs les plus proches, la plus proche superieure et la plus proche inférieure.

Là si on n'a pas le résultat, on fait une sorte de dichotomie, mais simplement entre l'ancienne valeur et l'une ou l'autre.. On n'a donc que des valeurs du tableau initial... Et une convergence que je ne saurais pas analyser, mais il me semble en O(1) : on cherche juste parmi les 2 points voisins..

J'ai l'impression que c'est équivalent à faire un équilibrage de deux listes "valeurs basses" et "valeurs hautes".

Code java :

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
int[] list = {12, 5, 6, 89, 5, 2390, 1};
 
List<Integer> low   = new LinkedList<Integer>();
List<Integer> high  = new LinkedList<Integer>();
 
// initial guess
int pivot = computeArithmeticMean(list);
for(int i=0;i<list.length;i++) 
	if (list[i]<=pivot) low.add(list[i]); else high.add(list[i]);
 
// Equilibrate the two lists by moving elements
while(low.size() < high.size()) {
	Integer minhigh = Collections.min(high);
	low.add(minhigh); high.remove(minhigh);
}
while(low.size() > high.size()) {
	Integer maxlow = Collections.max(low);
	low.remove(maxlow); high.add(maxlow);
}
 
// display median
Integer minhigh = Collections.min(high);
Integer maxlow  = Collections.max(low);
if (low.size()==high.size())
	System.out.println((maxlow+minhigh)*0.5);
else
	System.out.println(minhigh);

Auquel cas, je ne pense pas que la recherche des 2 candidats soit en O(1). C'est plutôt que tu profites de ta boucle d'équilibrage (en O(N)) pour identifier les 2 candidats.

[souviron34]

Envoyé par pseudocode

Auquel cas, je ne pense pas que la recherche des 2 candidats soit en O(1). C'est plutôt que tu profites de ta boucle d'équilibrage (en O(N)) pour identifier les 2 candidats.

Oui, j'aime bien le terme, et ça ressemble comme principe.... Bien que n'étant pas familier avec ces choes.....

Comme on n'ordonne pas, on est obligé de passer à travers tous les points, du coup j'ai encadré la valeur de référence par une valeur sup et une valeur inf..

Disons que je n'ai pas de gros tests à faire toruner, mais il me semble qu'au max on ne devrait tourner que très peu de fois (sans doute 2 itérations en moyenne) : soit on est au dessus et la valeur est celle du dessous, soit on est en dessous et la valeur est celle du dessus...

M'enfin, peut-être que je me trompe...


En fait, c'est comme si on avait ordonné et qu'on prenne le milieu, sauf qu'on n'ordonne pas et qu'on s'approche extrêmement vite.

Il faudrait tester sur de très grands tableaux... En fait vraisemblablement le pire cas serait avec plein de valeurs autour de la moyenne...


Bien entendu, on peut améliorer encore en divisant en intervalles (DPR)... Mais j'aime pas ce qui complique

Mais en tous cas ça me semble simple, sans tri, et rapide....

Quant à l'autre, avec un log double au lieu du log simple, ça devrait être pratiquement là aussi 2 itérations max.. (puisque là ça ferait log itéré 3 fois).. (mais faudrait régler le pbe des cas dégénérés impairs). Déjà avec un log simple pour des cas "normaux" (et pas du genre quil y a dans le test) ça devrait être très efficace.. (puisque c'est log(log))



C'était le fun à chercher une solution

[Celelibi]

Envoyé par souviron34

D'abord l'algo en O(N logc M)

La remarque de base est que pour classer des points, on a juste besoin d'une fonction croissante... Le log est une fonction croissante.. Là je présente avec un log simple, mais on peut augmenter en doublant, triplant, etc (mais ça fait des expression plus complquées).

La seconde remarque est que pour ne pas avoir de problèmes avec les logs, il faut que x soit > 0. Donc, dans le cas du log simple on se ramène à [1, +infini], pour le log double à [10, +infini], etc etc...

Enfin, ça marche par dichotomie comme indiqué dans un de mes premiers posts..

Note1 : comme je n'ai pas de 64 bits mais 32, j'ai testé avec 2^1000 et non 2^4000 ;

Note2 : il reste un cas à problème : les cas dégénérés dans le cas impair.. J'ai la femme .

Deux remarques sur la forme :
- Tu utilises un tableau temporaire. Donc quitte à avoir un algo qui nécessite un espace en O(N), autant faire un quickselect (qui sera en O(N) en temps) sur une copie du tableau.
Cela dit, il est facile dans ton code se passer de ce tableau en utilisant log(tab[i]-min+1) chaque fois que tu utilises temp[i].
- Je trouve que ta recherche de valeurs immédiatement supérieures et inférieures à la "médiane temporaire" est... compliquée. Ça n'est pourtant qu'une recherche de min et max.

Et sur le fond, ce qui me dérange dans ton algo, c'est qu'en prenant le log des valeurs du tableau, on perd en précision. Les double ne sont pas des réels, ni même des rationnels limités à un intervalle. C'est un truc complètement bâtard avec un nombre de bits de mantisse limité. En bref : dans le cas général, l'exponentielle du log n'est pas égale à la valeur de départ.

Mais même en imaginant qu'on ait des réels, prendre le log des valeurs ne fait que "resserrer" l'intervalle entre la valeur max et la valeur min.
Si tu travailles sur des double, ton algo initial (sans prendre le log des valeurs) est en O(N*log((max-min)/delta)) avec delta le plus petit écart entre deux valeurs consécutives qu'on va noter delta = d1 - d2.

Si tu travailles sur des entiers, delta = 1 et on avait noté précédemment max-min = M (sans le dire parce que c'était pas important).
Maintenant, avec le log des valeurs, ton algo est en O(N*log( log(max-min)/(log(d1)-log(d2)) ))
C'est pas très beau, on peut réécrire la partie à l'intérieur du premier log.
log(max-min)/(log(d1)-log(d2)) = log(M)/log(d1/d2)
Si d1 et d2 sont proches d1/d2 va tendre vers 1 par valeurs positives, donc log(d1/d2) va tendre vers 0. Donc log(M)/log(d1/d2) va augmenter rapidement quand d1 et d2 sont proches.

Donc si on met des valeurs assez proches, ça fait exploser le nombre d'itérations (quand ça termine). Par exemple : {0, 1e-16, 2e-16, 1, 2}, il trouve la médiane (dont la valeur est approximative) en 52 itérations.
(Parce que oui j'aime bien faire chier. )

Envoyé par souviron34

Algo linéaire O(N) : aucun cas particulier.

Le pirncipe de base est de trouver la moyenne, puis le point le plus proche dans le tableau (par valeur inférieure), puis à chaque fois qu'on explore de trouver les valeurs les plus proches, la plus proche superieure et la plus proche inférieure.

Là si on n'a pas le résultat, on fait une sorte de dichotomie, mais simplement entre l'ancienne valeur et l'une ou l'autre.. On n'a donc que des valeurs du tableau initial... Et une convergence que je ne saurais pas analyser, mais il me semble en O(1) : on cherche juste parmi les 2 points voisins..

Donc normalement on devrait avoir au plus un facteur constant de 4 pour les cas impairs et 6 pour les cas pairs...

J'ai du mal à comprendre ton "délire" avec les "Delta0" quand il s'agit de trouver la valeur immédiatement supérieure ou inférieure à une valeur donnée. D'ailleurs l'initialisation Delta0 = minval/10.0 va être foireuse pour un minval négatif.

Par contre cet algo c'est rien d'autre qu'une variante de l'algo dérivé du tri par sélection que j'ai présenté un peu plus haut. Il est en O(N²). Commencer avec la moyenne comme valeur initiale n'est qu'une heuristique. La médiane peut être aussi éloignée qu'on veut de la moyenne.
Par exemple {0, 1, 2, 3, 4, 5, ... k, 2^4000}. Cet algo va faire (k-1)/2 itérations (c'est à dire O(N)). Et dans chaque itération il recherche la valeur immédiatement inférieure (en O(N)).


Oui souviron, t'as tout à fait le droit de me trouver insolent. ^^

[souviron34]

Vite fait :

Envoyé par Celelibi

Deux remarques sur la forme :
- Tu utilises un tableau temporaire. Donc quitte à avoir un algo qui nécessite un espace en O(N), autant faire un quickselect (qui sera en O(N) en temps) sur une copie du tableau.
Cela dit, il est facile dans ton code se passer de ce tableau en utilisant log(tab[i]-min+1) chaque fois que tu utilises temp[i].

Oui, je l'avais noté au début de cette page (que ça pouvait être fait "in place") (post #46)

Envoyé par Celelibi

- Je trouve que ta recherche de valeurs immédiatement supérieures et inférieures à la "médiane temporaire" est... compliquée. Ça n'est pourtant qu'une recherche de min et max.

Pas tout à fait : c'est pour limiter la dichotomie à une valeur correcte. C'est le min de la partie supérieure et le max de la partie inférieure. Elle est un tout petit peu alambiquée à cause de la définition de la médiane dans les cas dégénérés (<= par rapport à < )

Envoyé par Celelibi

Et sur le fond, ce qui me dérange dans ton algo, c'est qu'en prenant le log des valeurs du tableau, on perd en précision. Les double ne sont pas des réels, ni même des rationnels limités à un intervalle. C'est un truc complètement bâtard avec un nombre de bits de mantisse limité. En bref : dans le cas général, l'exponentielle du log n'est pas égale à la valeur de départ.

On peut tout à fait s'en passer , et ne stocker que l'indice trouvé quand on cherche le plus proche en sortie. Et alors, au lieu de calculer l'exponentielle, on a la vraie valeur...

Envoyé par Celelibi

J'ai du mal à comprendre ton "délire" avec les "Delta0" quand il s'agit de trouver la valeur immédiatement supérieure ou inférieure à une valeur donnée. D'ailleurs l'initialisation Delta0 = minval/10.0 va être foireuse pour un minval négatif.

J'ai fait ça vite fait.. On peut redresser en valeurs positives en soustrayant (puis ajoutant) minval..

Le "délire" encore une fois est lié aux problèmes <= et <...

Envoyé par Celelibi

Oui souviron, t'as tout à fait le droit de me trouver insolent. ^^

loin de moi cette idée..

Je dis juste que c'est possible à faire, mais je n'ai pas que ça à faire, donc pour raffiner... Je présente une idée, sans plus.. Qui se passe de tris (ce qui était demandé) et semble tourner correctement (à quelques corrections à faire), tout en étant strictement < O(N2)...

[souviron34]

Bon, encore plus fort

En mixant les 2 approches :

Code C :

Moyenne 0.584856 et 1 iterations pour mediane
Tableau 1 mediane 2

Moyenne 0.415836 et 1 iterations pour mediane
Tableau 2 mediane 2

Moyenne 0.400515 et 1 iterations pour mediane
Tableau 3 mediane 2

Moyenne 0.345053 et 1 iterations pour mediane
Tableau 4 mediane 1.5

Moyenne 60.482 et 2 iterations pour mediane
Tableau 5 mediane 2

Moyenne 0.0752575 et 1 iterations pour mediane
Tableau 6 mediane 0

Moyenne 0.15563 et 1 iterations pour mediane
Tableau 7 mediane 2e-16

Moyenne 5.566 et 20 iterations pour mediane
Tableau 8 mediane 499998

(pour le dernier tableau, j'ai pris 1 million de points croissants jusqu'à 999998 plus 1 point à 2^1000)

[Celelibi]

Envoyé par souviron34

Bon, encore plus fort

En mixant les 2 approches

Effectivement, c'est une solution à laquelle j'avais vaguement pensé sans la formaliser. (Je me suis arrêté quand j'ai vu que sa complexité allait avoir un "min".)

À chaque itération tu élimines au moins une valeur du tableau, et t'espères en moyenne* en éliminer la moitié. C'est donc du O(N*min(N, log(M)/log(d1/d2))) ou un truc du genre. C'est donc au pire du O(N²).

Y'a juste un truc qui m'intrigue, c'est si on a plein de valeurs très proches et que le log les rend égales (parce qu'on est sur des double). Tu risques de pas pouvoir trouver la bonne valeur.

* Pour avoir un cas moyen il faut trouver une hypothèse moyenne de répartition des valeurs entre min et max. Répartition uniforme peut-être ?