Je sais qu'il est possible de calculer la moyenne d'une liste de nombres dans O (n). Mais qu'en est-il de la médiane? Y a-t-il un meilleur algorithme que de trier (O (N log n)) et d'un élément central de recherche (ou moyenne de deux éléments moyens si un nombre pair d'éléments de la liste)?
7 Réponses :
Ce lien a parcouru récemment sur le calcul de la médiane: http://matpalm.com/median/question .html .
En général, je pense que vous ne pouvez pas aller au-delà de l'heure (n log n), mais je n'ai aucune preuve à ce sujet :). Peu importe combien vous le faites parallèle, l'agrégation des résultats en une valeur unique prend au moins la journalisation N niveaux d'exécution.
J'ai changé votre réponse de "O (log n)" à "O (n log n)", ce que vous recherchiez, je pense, étant donné la question et le reste de votre réponse.
Ce lien entretient une "médiane des médianes", ou en d'autres termes, une approximation de la "vraie" médiane. Je ne suis pas sûr que c'est ce que l'OP demande.
Utilisation de la sélection déterministe, vous obtenez la vraie médiane. Voir ici: en.wikipedia.org/wiki/selection_algorithm
@Chris Jester-Young: Cela parle d'une "médiane des médianes", mais seulement comme une valeur intermédiaire dans l'algorithme - pas le résultat! Cet algorithme trouve la médiane (non médiane des médians) dans O (n), le pire des cas, le temps.
+1. Mais notez qu'il nécessite des comparaisons de 24n, ce qui signifie qu'il est susceptible d'être beaucoup plus lent que la méthode randomisée, qui moyenne de 1.5n comparaisons. (Nombres prises ou déduites des deux derniers paras de la page liée.)
Le lien est mort.
Si les chiffres sont discrets (par exemple, des entiers) et il existe un nombre gérable de valeurs distinctes, vous pouvez utiliser un "type de godet" qui est O (n), puis itérale sur les godets pour déterminer quel godet tient la médiane. . Le calcul complet est O (n) dans le temps et o (b) dans l'espace.
De quoi vous parlez est un algorithme de sélection , où k = n / 2 . Il existe une méthode basée sur la même fonction de partitionnement utilisé dans QuicksTort qui fonctionne. Il est appelé, sans surprise, QuickSelect . Bien que cela puisse, comme Quicksort, avoir un pire des cas O (N 2 ), cela peut être amené au temps linéaire en utilisant le Sélection de pivot .
partiellement non pertinent, mais: un embout rapide sur la manière de trouver rapidement des réponses aux questions de base courantes comme celle-ci sur le Web.
calcul efficace de l'échantillon médian même si le tri des éléments prend les opérations générales O (n log n), en utilisant un algorithme "Divide et Conquer", la médiane des n articles peut être calculée avec uniquement O (n) opérations (en fait, vous pouvez toujours Recherchez le k-ème élément d'une liste de valeurs avec cette méthode; ceci s'appelle le Problème de sélection ).
- Suivez le lien vers le problème de sélection pour la description de l'algorithme. Lire Intro:
... Il y a des algorithmes de sélection de temps linéaires les plus pauvres. ...
- et si vous êtes intéressé, lisez-vous sur le algorithme ingénieux .
Juste pour le plaisir (et qui sait, il peut être plus rapide), il existe un autre algorithme médian randomisé, expliqué techniquement dans le livre de Mitzenmacher et de Upfall. Fondamentalement, vous choisissez un sous-ensemble de la liste et (avec des reflet de fantaisie) de telle sorte qu'il contient probablement la vraie médiane, puis l'utiliser pour trouver la vraie médiane. Le livre est sur Google Books, et voici un Link . Remarque: j'ai pu lire les pages de l'algorthme, alors supposant que Google Books révèle les mêmes pages à tout le monde, vous pouvez les lire aussi.
C'est un algorithme aléatoire S.T. Si c'est trouve la réponse, il est certain de 100% qu'il s'agit de la réponse correcte (ceci s'appelle le style Las Vegas). Le hasard découle de la durée de l'exécution - à l'occasion (avec probabilité 1 / (SQRT (N)), je pense) Il ne trouve pas la médiane et doit être réutilisée.
asymptotiquement, il est exactement linéaire lorsque vous prenez la chance de défaillance - c'est un peu peu linéaire que linéaire, exactement de telle que lorsque vous prenez en compte le nombre de fois que vous devrez peut-être avoir besoin de Re-exécuter, il devient linéaire.
Remarque: Je ne dis pas que c'est mieux ou pire --- Je n'ai certainement pas fait de comparaison d'exécution réelle entre ces algorithmes! Je présente simplement un algorithme supplémentaire qui a une runtime linéaire, mais travaille de manière significativement différente.
Essayez l'algorithme randomisé, la taille d'échantillonnage (E.G. 2000) est indépendante de la taille de données N, peut toujours être en mesure d'obtenir une précision suffisamment élevée (99%). Si vous avez besoin d'une plus grande précision, augmentez simplement la taille d'échantillonnage. L'utilisation de CHEMINOFF Bound peut prouver la probabilité sous une certaine taille d'échantillonnage. J'ai écrit du code JavaScript pour implémenter l'algorithme, n'hésitez pas à le prendre. http://www.sfu.ca/~wpa10