La question est de savoir comment nous pouvons trouver la médiane d'un flux de réception de valeurs entières (par exemple pour 12, 14, 252, 243, 15, la médiane est de 15) dans Exemple: P> | Input | median
1 | 12 | 12
2 | 14 | 13 = (12+14)/2
3 | 252 | 14
.
.
.
3 Réponses :
(Je suppose que vous êtes après un algorithme qui, étant donné les numéros existants N et un nouveau numéro, prendra du temps logarithmique pour trouver la médiane de la nouvelle collection de N + 1 chiffres, de sorte que le temps d'exécution total pour l'ajout n sera o (n lg n) .)
Il y a probablement un algorithme nommé pour cela déjà, mais voici mon idée: maintenir un arbre noir rouge dans lequel vous insérez les chiffres à leur arrivée. Dans chaque noeud, en plus du nombre lui-même et des pointeurs enfants / parent, vous stockez un entier qui indique le nombre de nœuds existant sous ce nœud (y compris le nœud lui-même, pour la commodité). Je suis tout à fait certain que ces informations peuvent être mises à jour dans le temps logarithmique sur chaque opération d'insertion, même lorsque des rotations d'arbres sont nécessaires. Avec cette information intégrée dans l'arborescence, la localisation de la médiane peut être effectuée dans le temps logarithmique si vous gardez également une trace du nombre de nœuds dans l'arborescence.
(Cela pourrait être une description légèrement trop élevée; laissez-moi savoir si vous avez besoin de plus de détails.)
Vous avez absolument raison, j'essayais de faire exactement comme vous l'avez dit, mais le problème est que pour trouver la médiane uniquement en étiquetant le nombre d'enfants de chaque nœud est un peu difficile.
Ceci est décrit avec l'analyse complète dans: Introduction aux algorithmes (deuxième édition) - 14.3: Augmentation de structures de données - Arbres d'intervalles
@YI_H: Merci pour la référence.
@MAHD: Si vous avez, disons, 23 éléments, le 11ème élément (lors de la comptage de 0) est la médiane. Si l'enfant gauche du nœud racine dit que son sous-arbre contient 9 éléments, vous savez que la médiane n'est ni dans le sous-arbre de gauche, ni la racine, elle doit donc être dans le sous-arbre de droite, qui contient les 10ème à 22e éléments. Donc, par rapport à ce sous-arbre, vous recherchez maintenant le 1er élément. Exécuter cet algorithme récursivement.
Merci encore pour votre réponse, un autre problème ici est que, ce qui se passe si nous avons la même valeur (par exemple 10 8 7 7 5)
@MAHD: Le moyen le plus simple de gérer les numéros en double est probablement de les insérer en tant que nouveaux nœuds uniques. La règle standard pour tout type d'arborescence de recherche binaire est que tous les éléments du sous-arbre de gauche doivent être inférieurs à ou égal à l'élément de la racine, il est donc parfaitement admissible. Il est également possible de préférer avoir un champ Ofocurrences dans chaque nœud, mais la logique de recherche devient légèrement plus compliquée.
Algorithme de sélection de Hoare (aka QuickSelect) peut faire cela dans O ( n) temps moyen.
Il s'agit essentiellement de partitions récursives les données définies avec un pivot aléatoire et vérifie la partie appropriée. Il y a aussi un Médiane d'algorithme de médianes qui a garanti o (n) la plus grande complexité du temps, mais Pour l'utilisation normale, c'est généralement une overcilleuse.
Je pense qu'il recherche un algorithme en ligne qui, pour chaque nouveau numéro entré, peut produire la médiane de la nouvelle collection de chiffres. Cela peut être fait plus rapidement qu'avec Médian-Select.
Il n'a pas mentionné cela dans la question, si tel est le cas, les intervalles-intervalles sont parfaits ... et s'il n'a besoin que de la médiane de tout le flux, puis rapide ailleurs.
D'accord, avec la mise à jour de la question de sorte que l'intention est claire (pas seulement trouver la médiane, mais retrouvez la médiane à chaque fois que vous recevez un nouveau numéro), je pense qu'il y a un moyen.
Je commencerais par une paire de tas: un tas de max et un tas min-heat. Le Min-Heap contiendra les nombres plus grands que la médiane et le max-heape les nombres plus petits que la médiane. Lorsque vous recevez le premier numéro, c'est votre médiane. Lorsque vous recevez la seconde, vous insérez le plus petit des deux dans le tas Max-Heap et le plus grand des deux dans le Min-Heap. La médiane est alors la moyenne du plus petit sur le Min-Heap et le plus grand sur le tas Max-Heap.
Avec les deux tas, vous voudrez stocker un seul entier qui sera la médiane actuelle lorsque vous avez reçu un nombre impair d'intrants. Vous allez remplir cela assez simplement: si vous recevez une entrée avec elle, vous triez fondamentalement ces deux éléments (le nouveau numéro et l'ancienne médiane) et insérez le plus petit dans le tas pour les articles plus petits et les plus grands dans le tas. pour les éléments plus grands. Votre nouvelle médiane sera alors la moyenne des bases de ces deux tas (et vous ferez marquer l'autre emplacement de stockage comme vide).
Lorsque vous recevez un nouveau numéro avec celui vide, vous comparez le nouveau numéro à la médiane. Si c'est entre les chiffres comme bases des tas, c'est la nouvelle médiane et vous avez terminé. Sinon, extrayez le nombre de la base qui doit contenir la médiane (numéros plus importants si le nouveau numéro est plus grand, plus petit s'il est plus petit) et placez-le dans le point médian, puis insérez le nouveau numéro dans le tas de.
au moins si la mémoire sert, l'extrait / l'insertion dans un tas devrait être O (log n). Je crois que tout le reste impliqué devrait être une complexité constante.
Belle solution. (Je crois que l'extrait-min est également O (log n), ce qui ne modifie pas le comptoil global.)
Cette solution ne fonctionnera pas si la mémoire tampon du flux est finie et vous devez supprimer des éléments une fois que cela est plein dans l'ordre dans lequel il est entré. Les tas detamentent O (n) pour la recherche. Cependant, vous pouvez simplement utiliser une sorte d'arbre de recherche binaire au lieu d'un tas et que toutes les opérations seront O (log (n)).
À moins que les données soient triées et accessibles au hasard, je suis raisonnablement certain que vous pouvez espérer que la complexité linéaire est la complexité linéaire.
Bonjour Jerry, vous avez raison lorsque nous avons une liste de n valeurs, donc dans ce cas, nous devrions trier la liste (O (n log n)), mais comme je l'ai mentionné le problème ici est un peu différent, nous avons le flux d'intrants
Merci pour votre commentaire, j'ai fait
Nlogn est le moins