Existe-t-il des algorithmes ou des structures de données qui doivent trouver la valeur médiane d'un ensemble?

J'ai lu ce livre pour ma classe, Randomized Algorithms. Dans ce livre en particulier, il existe une section entière dédiée à la recherche de la médiane d'un tableau à l'aide de la sélection aléatoire, ce qui conduit à un algorithme plus efficace. Maintenant, je voulais savoir s'il existe des applications pratiques de cet algorithme, dans le domaine de l'informatique, en plus d'une amélioration théorique. Y a-t-il des algorithmes ou des structures de données qui doivent trouver la médiane d'un tableau?

s'il existe des applications pratiques de cet algorithme dans le domaine de l'informatique en plus d'être une amélioration théorique

L'application de cet algorithme est triviale - vous l'utilisez chaque fois que vous souhaitez calculer la médiane d'un ensemble de données (tableau en d'autres termes). Ces données peuvent provenir de différents domaines: observations astronomiques, sciences sociales, données biologiques, etc.

Cependant, il convient de mentionner quand préférer médiane signifie (ou mode). Fondamentalement, dans les statistiques descriptives, lorsque nos données sont parfaitement réparties normalement, la moyenne, le mode et la médiane sont égaux, c'est-à-dire qu'ils coïncident. D'un autre côté, lorsque nos données sont asymétriques, c'est-à-dire que la distribution de fréquence de nos données est (gauche / droite) asymétrique, la moyenne ne fournit pas le meilleur emplacement central parce que l'asymétrie les éloigne de la valeur typique vers la gauche ou la droite. , tandis que la médiane n'est pas aussi fortement influencée par les données asymétriques, et conserve donc mieux cette position pointant vers une valeur typique. Ainsi, le calcul d'une médiane peut être préférable lorsque vous traitez des données asymétriques.

En outre, l'apprentissage automatique est l'endroit où les méthodes statistiques sont largement utilisées, par exemple le clustering -medians .$k$

Le filtrage médian est courant dans la réduction de certains types de bruit dans le traitement d'image. Surtout le bruit du sel et du poivre. Il fonctionne en sélectionnant la valeur médiane dans chaque canal de couleur dans chaque voisinage local de l'image et en la remplaçant par elle. La taille de ces quartiers peut varier. Les tailles de filtres populaires (quartiers) sont par exemple 3x3 et 5x5 pixels.

Le calcul des médianes est particulièrement important dans les algorithmes randomisés.

Très souvent, nous avons un algorithme d'approximation qui, avec une probabilité d' au moins , donne une réponse à un facteur de de la vraie réponse  . Bien sûr, en réalité, nous voulons obtenir une réponse presque correcte avec une probabilité beaucoup plus élevée que . Nous répétons donc l'algorithme  fois, puis prenons la médiane. La médiane sera dans à moins qu'au moins la moitié des  échantillons soient inférieurs à ou au moins la moitié soit plus grande que , et cela a une probabilité exponentiellement petit en  . 1±ϵA$\tfrac34$$1\pm\epsilon$$A$ kA(1±ϵ)kA(1-ϵ)A(1+ϵ)$\tfrac34$$k$$A(1\pm\epsilon)$$k$$A(1-\epsilon)$$A(1+\epsilon)$$k$

Le calcul des médianes prend notre algorithme merdique «C'est faux une fois sur quatre» et le transforme en un algorithme «C'est faux une fois sur » tout en ajoutant seulement un facteur de quelque chose comme  au temps d'exécution.$2^n$$n$

La médiane des médianes a quelques applications:

• Recherche d'un pivot pour le tri rapide, qui apporte sa complexité la plus défavorable à .$O(n \log n)$
• Trouver un pivot pour la sélection rapide, apportant sa complexité au pire moment à , à partir de .O ( n 2$O(n)$$O(n^2)$