Trouvez médiane de tableau non trié dans

Pour trouver la médiane d'un tableau non trié, nous pouvons créer un min-tas en fois pour éléments, puis extraire un par un éléments pour obtenir la médiane. Mais cette approche prendrait temps. $O(n\log n)$ $n$ $n/2$ $O(n \log n)$

Peut-on faire la même chose par une méthode en temps? Si nous pouvons, alors comment? $O(n)$

algorithms time-complexity Luv
la source

en.wikipedia.org/wiki/Salection_algorithm

Jukka Suomela

@JukkaSuomela Pourquoi ne pas en faire une réponse simple et rapide (avec une courte explication d'un tel algorithme, idéalement)?

Raphaël

Notez la méta discussion connexe ; il s'avère que de simples recherches sur le Web mènent à la réponse à cette question.

Raphaël

stackoverflow.com/questions/2571358/median-of-a-billion-numbers

Evgeny

Réponses:

C'est un cas particulier d'un algorithme de sélection qui peut trouver le ème élément le plus petit d'un tableau, étant la moitié de la taille du tableau. Il existe une implémentation linéaire dans le pire des cas. $k$ $k$

Algorithme de sélection générique

Voyons tout d'abord un algorithme find-kthqui trouve le ème élément le plus petit d'un tableau: $k$

find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))

La fonction split(A, pivot)renvoie L,Rtelle que tous les éléments dedans Rsont plus grands que pivotet Ltous les autres (moins une occurrence de pivot). Ensuite, tout est fait récursivement.

C'est en moyenne mais dans le pire des cas. $O(n)$ $O(n^2)$

Le pire cas linéaire: l' algorithme de médiane des médianes

Un meilleur pivot est la médiane de toutes les médianes des sous-réseaux Ade taille 5, en appelant la procédure sur le tableau de ces médianes.

find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...

Ceci garantit dans tous les cas. Ce n'est pas si évident. Ces diapositives PowerPoint sont utiles pour expliquer l’algorithme et la complexité. $O(n)$

Notez que la plupart du temps, l'utilisation d'un pivot aléatoire est plus rapide.

jmad
la source

Cette taille est-elle 5standard? Et si la taille de A est inférieure à 5?

Jayesh

Pour tout n fixé, la complexité est constante, sauf si elle est infinie. Ainsi, vous pouvez utiliser n’importe quel algorithme valide de complexité finie pour un cas aussi spécial, même s’il s’agissait de O (2 ^ n). Pour un n fixé (c'est-à-dire au plus 4 dans notre cas), la complexité est au plus égale à 0 (2 ^ 4) = O (1).

v6ak

Sur le premier algorithme: return A[k]est incorrect (sauf s’il Aest trié, ce qui rendrait l’algorithme inutile). S'il splitest arrivé de diviser de Atelle sorte que k = |L| + 1vous ne sachiez toujours pas où se trouve l' kélément th. Votre cas de base est le moment où |A| = 1vous devez encore faire l'un des deux appels récursifs.

Wcochran

@ NickCaplinger corrigé avec web.archive.org

jmad

Le pire cas pour l'algorithme de sélection générique O (NlogN) n'est-il pas? Même si l'appel récursif ne laisse que 10% du tableau après chaque appel, il n'en reste pas moins un logarithme en base 10.

octavian

$n^{-1/4}$ $O(n)$

L'idée principale de l'algorithme est d'utiliser l'échantillonnage. Nous devons trouver deux éléments proches les uns des autres dans l'ordre trié du tableau et dont la médiane est située entre eux. Voir la référence [MU2017] pour une discussion complète.

[MU2017] Michael Mitzenmacher et Eli Upfal. "Probabilités et calcul: techniques de randomisation et probabilistes dans les algorithmes et l'analyse des données", chapitre 3, pages 57-62. Cambridge University Press, deuxième édition, 2017.

zdm
la source