Comment trouver les k voisins les plus proches de la médiane de n numéros distincts en O(n) le temps?
Je peux utiliser la médiane des médianes algorithme de sélection pour trouver la médiane en O(n). Aussi, je sais qu'une fois que l'algorithme est terminé, tous les éléments à gauche de la médiane sont moins que la médiane et tous les éléments à droite sont supérieures à la médiane. Mais comment puis-je trouver les k voisins les plus proches de la médiane en O(n) le temps?
Si la médiane est n, les nombres à gauche sont inférieurs à n et les chiffres à la droite sont plus grande que n.
Toutefois, le tableau n'est pas trié dans la gauche ou la droite. Les chiffres sont tout ensemble des différents chiffres donnés par l'utilisateur.
Le problème de l'Introduction des Algorithmes par Cormen, problème 9.3-7
Les chiffres sont bignums ou point fixe entiers?
OriginalL'auteur Anonymous | 2009-10-13
Vous devez vous connecter pour publier un commentaire.
Personne ne semble l'avoir. Voici comment le faire. Tout d'abord, trouver la médiane comme décrit ci-dessus. Ce est O(n). Maintenant le parc de la médiane à la fin du tableau, et de soustraire la médiane de tous les autres éléments. Maintenant, trouver l'élément k de la matrice (pas y compris le dernier élément), à l'aide de la sélection rapide de l'algorithme de nouveau. Ce n'est pas seulement trouve élément de k (dans l'ordre), il laisse aussi la matrice de sorte que le plus faible de k nombres sont au début de la matrice. Ce sont les k plus proches de la médiane, une fois que vous l'ajouter à la médiane du dos.
Si votre liste est (1,2,10,11,12), l'exécution d'un algorithme avec (k=2) de retour (1,2) au lieu de (11,12)
OriginalL'auteur HalPri
De la médiane-de-médianes n'a probablement pas beaucoup d'aide dans la recherche de l'voisins les plus proches, au moins pour n grand. Vrai, vous avez chaque colonne de 5 partitionné autour de la médiane, mais ce n'est pas de suffisamment d'informations pour la commande pour résoudre le problème.
Je venais de traiter la médiane comme un résultat intermédiaire, et de traiter les voisins les plus proches, comme une file d'attente prioritaire problème...
Une fois que vous avez la médiane de la médiane-de-médianes, de garder une note de sa valeur.
Exécuter le heapify algorithme sur l'ensemble de vos données - voir Wikipédia - Tas Binaire. Dans les comparaisons, de base le résultat de la différence par rapport à celui enregistré valeur médiane. La priorité la plus élevée éléments sont ceux avec le plus bas ABS(valeur médiane). Cela prend un temps O(n).
Le premier élément du tableau est maintenant la médiane (ou une reproduction de celle-ci), et la matrice a des tas de structure. Utilisez le tas extrait de l'algorithme pour enlever le nombre de plus proches voisins que vous en avez besoin. Ce est O(k log n) pour k plus proches voisins.
Tant que k est une constante, vous obtenez O(n), la médiane des médianes, O(n) heapify et O(log n) l'extraction, donnant à O(n) dans l'ensemble.
Si vous le faites de la muette chemin (l'insertion de chaque élément à son tour dans un vide au début segment de mémoire), c'est O(n log n). Si vous utilisez le heapify algorithme est O(n). Voir la page de wikipédia ("la Construction d'un segment de mémoire" de la section) pour plus de détails.
Pourquoi peut-on traiter k une constante? Que faire si
k == n
?Tout d'abord, lors de la spécification de la complexité des algorithmes, à moins d'indication contraire,
k
est par convention commune supposé être une constante indépendante den
. Aussi, dans le problème par la convention connu comme "k plus proches voisins",k
représente toujours le nombre de voisins à trouver, ce qui est toujours constant (au moins dans le sens de l'indépendance-de-moins-en cours-bornée par le nombre total de sommetsn
). Et ce n'est pas une coïncidence: il y a une beaucoup plus large de la convention quik
représente une constante, indépendante des autres variables.OriginalL'auteur Steve314
OriginalL'auteur Gaurav Pandey
Vous pouvez résoudre votre problème comme ça:
Vous pouvez trouver la médiane en O(n), w.g. à l'aide de l'O(n) nth_element algorithme.
Vous parcourir tous les éléments substutiting chacun avec une paire de:
Une fois de plus vous ne nth_element avec n = k. après l'application de cet algorithme, vous êtes assuré d'avoir le k éléments les plus petits en valeur absolue de la différence première du nouveau tableau. Vous prenez les indices et FAIT!
ok je n'ai pas le lire, puis, merci pour le tuyau
C'est mieux que @HalPri réponse - @Shivendra est à l'aide de
absoulte difference
, ce qui résout le problème je l'ai souligné dans mon commentaire de @HalPri réponseOriginalL'auteur Shivendra
Vous pouvez utiliser un non-comparaison de la sorte, comme une base de tri, sur la liste des numéros de
L
, puis de trouver les k voisins les plus proches en considérant windows de k éléments et l'examen de la fenêtre des points de terminaison. Une autre façon de dire "trouver la fenêtre" est de trouver i qui minimiseabs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i] - L[n/2])
(si k est impair) ouabs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i+1] - L[n/2])
(si k est pair). En combinant les cas,abs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i+!(k&1)] - L[n/2])
. Un simple, O(k) moyen de trouver le minimum est de commencer avec i=0, puis faites glisser vers la gauche ou la droite, mais vous devriez être capable de trouver le minimum en O(log(k)).L'expression de minimiser provient de la transformation de
L
dans une autre liste,M
, en prenant la différence de chaque élément de la médiane.i
minimiseM[n/2-k/2+i] + M[n/2+k/2+i]
.OriginalL'auteur outis
Vous savez déjà comment faire pour trouver la médiane en O(n)
si l'ordre n'a pas d'importance, la sélection des k plus petit peut être fait en O(n)
appliquer pour les k plus petit pour le membre de droite de la médiane et des k plus à gauche de la médiane
à partir de wikipedia
ne pas oublier le cas particulier où k==n retour à la liste originale
OriginalL'auteur John La Rooy
En fait, la réponse est assez simple. Tout ce que nous devons faire est de choisir k éléments avec la plus petite des différences absolues de la médiane du déplacement de m-1 à 0 et m+1 à n-1 lorsque la médiane est à l'index m. Nous avons sélectionnez les éléments à l'aide de la même idée que nous utilisons dans la fusion de 2 tableaux triés.
OriginalL'auteur Anonymous
Quatre Étapes:
OriginalL'auteur Jimmy
Si vous connaissez l'index de la médiane, ce qui devrait être ceil(tableau.longueur/2) peut-être, puis il devrait y avoir un processus de cotation n(x-k) n(x-k+1), ... , n(x) n(x+1), n(x+2), ... n(x+k)
où n est la matrice x est l'indice de la médiane, et k est le nombre de voisins dont vous avez besoin.(peut-être k/2, si vous voulez le total k non k de chaque côté)
Ah, toutes mes excuses. J'ai lu la question originale à la version 2, où il a ajouté qu'il avait déjà triés dans l'ordre.
OriginalL'auteur glasnt
Sélectionnez d'abord la médiane dans
O(n)
temps, à l'aide d'un algorithme standard de cette complexité.Puis exécutez à travers la liste de nouveau, en sélectionnant les éléments qui sont le plus proche de la médiane (en stockant le plus connu des candidats et de comparer les nouvelles valeurs à l'égard de ces candidats, de même que l'on cherche pour un élément maximal).
Dans chaque étape de cette course supplémentaire par le biais de la liste O(k) étapes sont nécessaires, et puisque k est constant ce est O(1). De sorte que le total pour le temps nécessaire pour la course supplémentaire est O(n), comme c'est le total d'exécution de l'intégralité de l'algorithme.
OriginalL'auteur sth
Puisque tous les éléments sont distincts, il peut être antérieure au plus 2 éléments avec la même différence de la moyenne. Je pense que c'est plus facile pour moi d'avoir 2 tableaux A[k] et B[k] l'indice représentant la valeur absolue de la différence de la moyenne. Maintenant, la tâche est seulement pour remplir les tableaux et choisir k éléments par la lecture de la première k non vide, les valeurs des tableaux de la lecture d'Un[i] et B[i] devant Un[i+1] et B[i+1]. Cela peut être fait en O(n) fois.
programmeur: uniquement si vous êtes en train de faire une comparaison de tri.
Cela fonctionne si les nombres sont des nombres entiers
OriginalL'auteur Anonymous