Znaleźć medianę niesegregowanych tablicy w

Aby znaleźć medianę nieposortowanej tablicy, możemy wykonać min-stos w czasie dla elementów, a następnie możemy wyodrębnić jeden po drugim elementów, aby uzyskać medianę. Ale takie podejście zająłoby czas . $O(n\log n)$ $n$ $n/2$ $O(n \log n)$

Czy możemy zrobić to samo za pomocą jakiejś metody w czasie ? Jeśli możemy, to jak? $O(n)$

algorithms time-complexity Luv
źródło

en.wikipedia.org/wiki/Selection_algorithm

Jukka Suomela

@JukkaSuomela Dlaczego nie uczynić to szybką i prostą odpowiedzią (najlepiej z krótkim wyjaśnieniem jednego z takich algorytmów)?

Raphael

Zwróć uwagę na powiązaną meta dyskusję ; jak się okazuje, proste wyszukiwania w sieci prowadzą do odpowiedzi na to pytanie.

Raphael

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

Evgeny

Odpowiedzi:

Jest to szczególny przypadek algorytmu selekcji, który może znaleźć ty najmniejszy element tablicy za pomocą $k$ $k$ czyli połowę wielkości tablicy. W najgorszym przypadku istnieje implementacja liniowa.

Ogólny algorytm selekcji

Najpierw zobaczmy algorytm, find-kthktóry znajduje ty najmniejszy element tablicy: $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))

Funkcja split(A, pivot)zwraca L,Rtak, że wszystkie elementy Rsą większe niż pivoti Lwszystkie inne (minus jedno wystąpieniepivot ). Następnie wszystko odbywa się rekurencyjnie.

Jest to w średniej, ale w najgorszym przypadku. $O(n)$ $O(n^2)$

Najgorszy przypadek liniowy: algorytm mediany median

Lepszym punktem obrotu jest mediana wszystkich median podtablic o Arozmiarze 5, poprzez wywołanie procedury na tablicy tych median.

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

To gwarantuje we wszystkich przypadkach. To nie jest takie oczywiste. Te slajdy PowerPoint są pomocne zarówno w wyjaśnieniu algorytmu, jak i złożoności. $O(n)$

Zauważ, że przez większość czasu korzystanie z losowego obrotu jest szybsze.

jmad
źródło

Czy ten rozmiar jest 5standardowy? Co jeśli rozmiar A jest mniejszy niż 5?

Jayesh

Dla dowolnego stałego n złożoność jest stała, chyba że jest nieskończona. Możesz więc użyć dowolnego poprawnego algorytmu o skończonej złożoności dla takiego specjalnego przypadku, nawet jeśli byłby to O (2 ^ n). Dla stałej n (tj. Maksymalnie 4 w naszym przypadku) złożoność wynosi co najwyżej O (2 ^ 4) = O (1).

v6ak 23.04.16

W przypadku pierwszego algorytmu: return A[k]jest niepoprawny (chyba że Ajest posortowany, co spowodowałoby, że algorytm byłby dyskusyjny). Jeśli splitzdarzyło Ci się podzielić Atak, k = |L| + 1że nadal nie wiesz, gdzie jest ten kelement. Podstawowym przypadkiem jest sytuacja, gdy |A| = 1jeszcze trzeba wykonać jedno z dwóch połączeń rekurencyjnych.

wcochran

@NickCaplinger naprawiono za pomocą web.archive.org

jmad

Czy nie jest najgorszym przypadkiem dla ogólnego algorytmu wyboru O (NlogN)? Nawet jeśli rekurencyjne wywołanie pozostawia tylko 10% tablicy po każdym wywołaniu, to nadal jest to logarytm na podstawie 10.

octavian

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

Główną ideą algorytmu jest wykorzystanie próbkowania. Musimy znaleźć dwa elementy, które są blisko siebie w posortowanej kolejności tablicy i które mają medianę między nimi. Pełna dokumentacja znajduje się w odnośniku [MU2017].

[MU2017] Michael Mitzenmacher i Eli Upfal. „Prawdopodobieństwo i obliczenia: randomizacja i techniki probabilistyczne w algorytmach i analizie danych”, rozdział 3, strony 57–62. Cambridge University Press, drugie wydanie, 2017 r.

zdm
źródło