Médiane des médianes
algorithme de sélection / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Médiane des médianes?
Résumez cet article pour un enfant de 10 ans
Pour les articles homonymes, voir Médiane.
En informatique, la médiane des médianes est un algorithme de sélection pour trouver le k-ième élément le plus grand au sein d'un tableau initialement 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 de la médiane des médianes fut publié par Blum, Floyd, Pratt (en), Rivest et Tarjan en 1973 dans Time bounds for selection[2], et est parfois appelé BFPRT d'après les initiales des noms des auteurs.
Découvreurs ou inventeurs |
Manuel Blum, Robert Floyd, Vaughan Pratt (en), Ronald Rivest, Robert Tarjan |
---|---|
Date de découverte | |
Problème lié | |
Structure des données | |
Basé sur |
Pire cas | |
---|---|
Meilleur cas |
Pire cas |
---|