Accueil🇫🇷Chercher

Médiane des médianes

La médiane des médianes est un algorithme de sélection pour trouver le kième élément le plus grand au sein d'une liste non triée. Il est basé sur l'algorithme Quickselect. Cet algorithme est optimal dans le pire cas, avec une complexité en temps linéaire. La brique de base de l'algorithme est la sélection d'une médiane approchée en temps linéaire. L'algorithme est parfois appelé BFPRT d'après les noms des auteurs : Blum, Floyd, Pratt (en), Rivest et Tarjan.

Médiane des médianes
Découvreurs ou inventeurs
Date de découverte
Problème lié
Structure des données
Basé sur
Complexité en temps
Pire cas
Meilleur cas
Complexité en espace
Pire cas

Principe général de l'algorithme

L'algorithme se déroule en 3 étapes :

  • L'algorithme divise la liste en groupes de cinq éléments. Ensuite, pour chaque groupe de cinq, la médiane est calculée (une opération qui peut s'effectuer en temps constant, par exemple en utilisant un algorithme de tri[2]).
  • L'algorithme est alors appelé récursivement sur cette sous-liste de éléments pour trouver la vraie médiane de ces éléments. On peut alors garantir que l'élément obtenu se place entre le 30e et le 70e centile.
  • Enfin, la médiane des médianes est choisie pour être le pivot. Selon la position de l'élément recherché, l'algorithme recommence avec les éléments au-dessus du pivot ou en dessous, qui représentent au plus 70 % de la taille initiale de l'espace de recherche.

Propriétés du pivot

Parmi les groupes, la moitié ont leur médiane en dessous du pivot (la médiane des médianes), ce qui garantit au moins éléments en dessous du pivot (3 parmi chacun des groupes). Ainsi, le pivot choisi est à la fois inférieur à environ éléments et plus grand que éléments. Ainsi, la médiane divise les éléments choisis quelque part entre 30 %70 % et 70 %30 %, ce qui assure dans le pire des cas un comportement linéaire de l'algorithme. Pour visualiser :

Une itération des deux premières étapes de l'algorithme sur {0,1,2,3,...99}
121511295073214440118203219353739
1316148102663342749465225513443567279
Médianes 1723242829303136424750555860636566678183
2245385361416282544859577178648070768587
9695948689696897739274889984759077939891

En rouge, la médiane des médianes.

Preuve du O(n)

Avec le temps d’exécution de l'algorithme sur une entrée de taille , on a la récurrence suivante:

  • le terme est la recherche de la médiane parmi les médianes de quintuplet.
  • le terme est le coût du travail de partitionnement autour du pivot.
  • le terme est l'appel récursif (dans le pire cas) pour trouver le ke élément dans la partition correspondante.

De cette formule on vérifie simplement par récurrence :

Autres usages de la médiane

La sélection d'une médiane approchée en temps linéaire peut aussi être utilisée pour garantir au tri rapide une complexité en dans le pire cas. Dans les deux cas, l'utilisation de la médiane est en moyenne moins efficace que le choix d'un pivot aléatoire, qui évite le surcoût du calcul du pivot.

Histoire

L'algorithme de la médiane des médianes fut publié par Blum, Floyd, Pratt (en), Rivest et Tarjan en 1973 dans Time bounds for selection[3], et est parfois appelé BFPRT d'après les noms des auteurs.

Voir aussi

Notes et références

  1. (en) Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest et Robert E. Tarjan, « Time bounds for selection », Journal of Computer and System Sciences, Elsevier, vol. 7, no 4, , p. 448-461 (ISSN 0022-0000 et 1090-2724, DOI 10.1016/S0022-0000(73)80033-9)
  2. (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press, , 3e éd. [détail de l’édition]
  3. (en) M. Blum, R. W. Floyd, V. Pratt, R. Rivest et R. Tarjan, « Time bounds for selection », J. Comput. System Sci., vol. 7, , p. 448-461
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.