Mediana median

Mediana Median
Klasa	Algorytm wyboru
Struktura danych	Szyk
Wydajność w najgorszym przypadku
Najlepsza wydajność
Złożoność przestrzeni w najgorszym przypadku	pomocniczy

W informatyce mediana median mediany jest przybliżonym algorytmem wyboru , często używanym do zapewnienia dobrego obrotu dla algorytmu dokładnego wyboru, najczęściej quickselect , który wybiera k- ty najmniejszy element z początkowo nieposortowanej tablicy. Mediana median znajduje przybliżoną medianę w czasie liniowym. Używając tej przybliżonej mediany jako ulepszonego obrotu, złożoność szybkiego wyboru w najgorszym przypadku zmniejsza się z kwadratowej do liniowej , co jest również asymptotycznie optymalną złożonością najgorszego przypadku dowolnego algorytmu selekcji. Innymi słowy, mediana median jest przybliżonym algorytmem selekcji medianowej, który pomaga zbudować asymptotycznie optymalny, dokładny ogólny algorytm selekcji (szczególnie w sensie złożoności najgorszego przypadku), tworząc dobre elementy obrotu.

Mediana median może być również używana jako strategia przestawna w sortowaniu szybkim , dając optymalny algorytm o złożoności najgorszego przypadku ${\ Displaystyle O (n \ log n)}$ . Chociaż to podejście dość dobrze optymalizuje asymptotyczną złożoność $wyboru$ lepsze wyniki, zamiast tego wybierając losowe punkty obrotu dla jego średniej i $sortowania$ , bez narzutu związanego z obliczaniem osi obrotu.

Podobnie mediana median jest używana w hybrydowym algorytmie introselect jako rezerwa dla wyboru przestawnego w każdej iteracji, aż do znalezienia k-tej najmniejszej. To ponownie zapewnia liniową wydajność w najgorszym przypadku, oprócz wydajności liniowej w przypadku średniej: introselect rozpoczyna się od szybkiego wyboru (z losowym obrotem, domyślnie), aby uzyskać dobrą średnią wydajność, a następnie powraca do zmodyfikowanego szybkiego wyboru z obrotem uzyskanym z mediany mediany, jeśli postęp jest zbyt wolny. Chociaż taki algorytm hybrydowy jest asymptotycznie podobny, będzie miał mniejszą złożoność niż prosty wybór wewnętrzny aż do stałego współczynnika (zarówno w przypadku średnim, jak i najgorszym), przy dowolnej skończonej długości.

Algorytm został opublikowany w Blum et al. (1973) i dlatego jest czasami nazywany BFPRT od nazwisk autorów. W oryginalnym artykule algorytm był określany jako PICK , odnosząc się do szybkiego wyboru jako „ZNAJDŹ”.

Motywacja

Szybki wybór działa średnio w czasie liniowym, ale może wymagać czasu kwadratowego przy złych wyborach obrotu. $,$ ponieważ quickselect to algorytm typu „ i rządź” którym każdy krok zajmuje czas w rozmiarze pozostałego zestawu wyszukiwania. Jeśli rozmiar zbioru wyszukiwania zmniejsza się wykładniczo szybko (o ustaloną proporcję), daje to szereg geometryczny pomnożony przez ${\ Displaystyle O (n)}$ czynnik pojedynczego kroku, a tym samym liniowy całkowity czas. Jeśli jednak zbiór wyszukiwania zmniejsza się powoli, na przykład liniowo (o ustaloną liczbę elementów, w najgorszym przypadku zmniejszając się tylko o jeden element za każdym razem), wówczas liniowa suma kroków liniowych daje kwadratowy całkowity czas (formalnie trójkątny liczby rosną kwadratowo). Na przykład najgorszy przypadek występuje podczas obracania na najmniejszym elemencie na każdym kroku, na przykład poprzez zastosowanie szybkiego wyboru dla maksymalnego elementu do już posortowanych danych i za każdym razem przyjmowanie pierwszego elementu jako elementu obrotowego.

Jeśli zamiast tego konsekwentnie wybiera się „dobre” obroty, można tego uniknąć i zawsze uzyskuje się liniową wydajność, nawet w najgorszym przypadku. „Dobry” obrót to taki, dla którego możemy ustalić, że stała proporcja elementów spada zarówno poniżej, jak i powyżej, ponieważ wtedy zbiór wyszukiwania zmniejsza się co najmniej o stałą proporcję na każdym kroku, a więc wykładniczo szybko, a całkowity czas pozostaje liniowy. Mediana jest dobrym punktem zwrotnym — najlepszym do sortowania i najlepszym ogólnym wyborem do wyboru — zmniejszającym zestaw wyszukiwania o połowę na każdym kroku. Tak więc, jeśli można obliczyć medianę w czasie liniowym, dodaje to tylko czas liniowy do każdego kroku, a zatem ogólna złożoność algorytmu pozostaje liniowa.

Algorytm mediany median oblicza przybliżoną medianę, czyli punkt, który z pewnością mieści się między 30. a 70. percentylem (w środku 4 decyle ). W ten sposób zestaw wyszukiwania zmniejsza się o co najmniej 30%. Problem zostaje zredukowany do 70% pierwotnego rozmiaru, czyli o stałą proporcję mniejszego rozmiaru. Zastosowanie tego samego algorytmu na teraz mniejszym zbiorze rekurencyjnie, aż pozostanie tylko jeden lub dwa elementy, skutkuje kosztem ${\ Displaystyle {\ Frac {n} {1-0,7}} \ około 3,33 {n} }$

Algorytm

Jak wspomniano wcześniej, mediana median jest używana jako strategia wyboru przestawnego w algorytmie szybkiego wyboru , który w pseudokodzie wygląda następująco. Uważaj, aby obchodzić się z left , right i n podczas wdrażania. Poniższy pseudokod zakłada, że left , right i lista używają numeracji opartej na jedynkach i że select jest początkowo wywoływany z 1 jako argumentem po lewej i długością listy jako argumentem po prawej . Zauważ, że to zwraca indeks n-tej najmniejszej liczby po zmianie układu listy, zamiast rzeczywistej wartości n-tej najmniejszej liczby.

        
            
             funkcja  select(lista, left, right, n)  pętla  jeśli  left = right  to  return  left pivotIndex := pivot(lista, left, right) pivotIndex := partition(lista, left, right, pivotIndex, n)  if  n = pivotIndex  to  zwróć  n  w przeciwnym razie  , jeśli  n <Indeksprzestawny,  a następnie  w prawo :=Indeksprzestawny - 1  w przeciwnym razie, w  lewo :=Indeksprzestawny + 1

Zwrot podprogramu to rzeczywisty algorytm mediany median. Dzieli swoje dane wejściowe (listę o długości $n$ ) na grupy co najwyżej pięciu elementów, oblicza medianę każdej z tych grup za pomocą jakiejś podprogramu, a następnie rekurencyjnie oblicza prawdziwą medianę ${\ displaystyle {\ frac {n} {5}}}$ mediany znalezione w poprzednim kroku:. Zauważ, że wywołania przestawne wybierają ; jest to przykład wzajemnej rekurencji .

    
        
     funkcja  pivot(lista, left, right)  // dla 5 lub mniej elementów po prostu pobierz medianę,  jeśli  right − left < 5,  a następnie  zwróć  partition5(list, left, right)  // w przeciwnym razie przenieś mediany pięcioelementowych podgrup do pierwszego n /5 pozycji  dla  i  od  lewej  do  prawej  w krokach co  5  // uzyskaj środkową pozycję i-tej podgrupy pięcioelementowej  subRight := i + 4  if  subRight > right  then  subRight := prawa mediana5 := partition5(list, i, subRight) swap list[mediana5] and list[left + floor((i − left)/5)] // oblicz medianę  z n/5 median-of- pięć  środkowych := (prawo - lewo) / 10 + lewo + 1  powrót  wybierz (lista, lewo, lewo + podłoga ((prawo - lewo) / 5), środek)

Funkcje pomocnicze partycji

Istnieje podprogram o nazwie partition , który może w czasie liniowym grupować listę (od indeksów od lewej do prawej ) na trzy części, mniejsze od określonego elementu, równe jemu i większe od elementu ( trój- partycja kierunkowa ). Grupowanie na trzy części zapewnia, że mediana median zachowuje liniowy czas wykonania w przypadku wielu lub wszystkich zbieżnych elementów. Oto pseudokod, który wykonuje partycję dotyczącą elementu list[pivotIndex] :

    
        
     function  partition(list, left, right, pivotIndex, n) pivotValue := list[pivotIndex] swap list[pivotIndex] i list[right] // Przenieś element przestawny  na koniec  storeIndex := lewo  // Przenieś wszystkie elementy mniejsze od elementu przestawnego do po lewej stronie osi obrotu  dla  i  od  lewej  do  prawej − 1  wykonaj  if  lista[i] < wartość obrotu  następnie  zamień listy[storeIndex] i list[i] increment storeIndex  // Przenieś wszystkie elementy równe osi obrotu zaraz po  // mniejszych elementach 
        
    
    
        
     storeIndexEq = storeIndex  dla  i  od  storeIndex  w  prawo − 1  wykonaj  if  lista[i] = pivotValue  następnie  zamień list[storeIndexEq] i list[i] inkrementuj storeIndexEq swap list[right] i list[storeIndexEq]  // Przenieś element przestawny na ostatnie miejsce  // Zwróć położenie przestawne z uwzględnieniem żądanej lokalizacji n  if  n < storeIndex  then  return  storeIndex  // n należy do grupy mniejszych elementów  if  n ≤ storeIndexEq 
        
     wtedy  return  n  // n jest w grupie równej przestawie  return  storeIndexEq  // n jest w grupie większych elementów

Podprogram partition5 wybiera medianę grupy maksymalnie pięciu elementów; łatwym sposobem na wdrożenie tego jest sortowanie przez wstawianie , jak pokazano poniżej. Może być również zaimplementowany jako drzewo decyzyjne .

 funkcja  partycja5( lista, lewa, prawa) i := lewa + 1  podczas gdy  i ≤ prawa j := i  podczas gdy  j > lewa i lista[j−1] > lista[j]  do  zamiany lista[j−1] i lista[ j] j := j − 1 i := i + 2  powrót  piętro((lewo + prawo) / 2)

Właściwości obrotu

Z grup ${\ Displaystyle {\ Frac {n} {5}}}$ , połowa liczby grup ( ${\ Displaystyle {\ Frac {1} {2}} \ razy { \frac {n}{5}}={\frac {n}{10}}}$ ) mają medianę mniejszą niż oś obrotu (mediana median). Również kolejna połowa liczby grup (ponownie, ${\ Displaystyle {\ Frac {1} {2}} \ razy {\ Frac {n} {5}} = {\ Frac {n }{10}}}$ ) mają medianę większą niż przestawna. W każdym z ${\ Displaystyle {\ Frac {n} {10}}}$ grup z medianą mniejszą niż oś obrotu, istnieją dwa elementy, które są mniejsze niż ich odpowiednie mediany, które są mniejsze niż oś obrotu. Zatem każda z grup ma co najmniej 3 elementy mniejsze niż $.$ Podobnie, w każdej z grup z medianą większą niż $obrotu$ obrotu, istnieją dwa elementy, które są większe niż odpowiadające im mediany, które są większe niż oś Zatem każdy z ${\ displaystyle {\ frac {n} {10}}}$ grupy mają co najmniej 3 elementy większe niż oś obrotu. W związku z tym $Displaystyle 3 \ razy {\ frac {$ obrotu jest mniejsza niż elementy i większa niż inne $elementy 3$ elementów. Zatem wybrana mediana dzieli uporządkowane elementy gdzieś pomiędzy 30%/70% a 70%/30%, co zapewnia najgorsze liniowe zachowanie algorytmu. Aby zwizualizować:

Jedna iteracja na losowym zbiorze 100 elementów od 0 do 99
	12	15	11	2	9	5	0	7	3	21	44	40	1	18	20	32	19	35	37	39
	13	16	14	8	10	26	6	33	4	27	49	46	52	25	51	34	43	56	72	79
Mediany	17	23	24	28	29	30	31	36	42	47	50	55	58	60	63	65	66	67	81	83
	22	45	38	53	61	41	62	82	54	48	59	57	71	78	64	80	70	76	85	87
	96	95	94	86	89	69	68	97	73	92	74	88	99	84	75	90	77	93	98	91

(czerwony = „(jedna z dwóch możliwych) mediana median”, szary = „liczba < czerwony”, biały = „liczba > czerwony”)

Dla przejrzystości pokazano tutaj 5 krotek posortowanych według mediany. Sortowanie krotek nie jest konieczne, ponieważ potrzebujemy tylko mediany do użycia jako elementu przestawnego.

Zwróć uwagę, że wszystkie elementy powyżej/na lewo od czerwieni (30% ze 100 elementów) są mniejsze, a wszystkie elementy poniżej/na prawo od czerwieni (kolejne 30% ze 100 elementów) są większe.

Dowód czasu działania O( n ).

$liniowego najgorszego przypadku$ ponieważ lista median ma rozmiar , gdy inne wywołanie rekurencyjne powtarza się co najwyżej w 70% Lista. Niech będzie czasem potrzebnym do uruchomienia algorytmu mediany median Quickselect na tablicy o rozmiarze T ( $T ($ $\ displaystyle$ . Wtedy wiemy, że tym razem jest:

{\ Displaystyle T (n) \ równoważnik T (n/5) + T (n \ cdot 7/10) +c\ckropka n,}

Gdzie

część służy do znalezienia $Frac$ mediany n $n} {5} }}$ mediany, uruchamiając na nich (niezależny) Quickselect (ponieważ znalezienie mediany to tylko specjalny przypadek wybrania k - najmniejszego elementu)
termin służy do dzielenia, aby utworzyć dwie strony, z których jedna będzie się powtarzać w naszym Quickselect (odwiedziliśmy każdy element jako stałą O ( n $O$ $)$ $)$ aby utworzyć je w n/5 grup i wziąć każdą medianę w .
$część dotyczy rzeczywistej rekurencji Quickselect$ w najgorszym przypadku w element jest większa partycja, która może mieć maksymalny rozmiar ${\ displaystyle {\ frac {7n} {10}}}$

Przez indukcję:

{\ Displaystyle T (n) \ równoważnik 10 \ cdot c \ cdot n \ w O (n).}

Analiza

Kluczowym krokiem jest zredukowanie problemu do wyboru z dwóch list, których całkowita długość jest krótsza niż oryginalna lista, plus współczynnik liniowy dla kroku redukcji. Pozwala to na prostą indukcję, aby pokazać, że całkowity czas działania jest liniowy.

Konkretny wybór grup pięciu elementów wyjaśniono w następujący sposób. Po pierwsze, obliczenie mediany listy nieparzystej jest szybsze i prostsze; chociaż można by użyć listy parzystej, wymaga to wzięcia średniej z dwóch środkowych elementów, co jest wolniejsze niż po prostu wybranie jednego dokładnie środkowego elementu. Po drugie, pięć to najmniejsza liczba nieparzysta, dla której działa mediana median. $. ułamek {2}{3}}n}$ tylko z trzech elementów, wynikowa lista median do wyszukiwania ma długość $i$ listę do rekurencyjnej , ponieważ jest większy niż 1/2 × 2/3 = 1/3 elementów i mniejszy niż 1/2 × 2/3 = 1/3 elementów. W związku z tym nadal pozostawia $przeszukania$ , co nie zmniejsza wystarczająco problemu. Poszczególne listy są jednak krótsze i wynikową złożoność można powiązać $nie$ Bazzi ale to liniowości

I odwrotnie, zamiast tego można pogrupować według $=$ , dziewięć lub więcej elementów i to działa. Zmniejsza to rozmiar listy median do $ponieważ$ a rozmiar listy do rekurencji w asymptoty po 3 / 4 (75%), ćwiartki w powyższej tabeli około 25%, ponieważ rozmiar nakładających się linii zmniejsza się proporcjonalnie. Zmniejsza to asymptotycznie współczynnik skalowania z 10 do 4, ale odpowiednio podnosi do $}$ termin na prace rozbiorowe. Znalezienie mediany większej grupy zajmuje więcej czasu, ale jest czynnikiem stałym (zależnym tylko od $,$ a zatem nie zmienia ogólnej wydajności wraz ze wzrostem n . W rzeczywistości, biorąc pod uwagę liczbę porównań w najgorszym przypadku, współczynnik stały wynosi ${\ Displaystyle {\ Frac {2g (g-1)} {g-3}}}$ .

Jeśli zamiast tego pogrupuje się w inny sposób, powiedzmy, dzieląc $5$ list, obliczając medianę każdej z nich, a następnie obliczając medianę z nich - tj. Grupując według stałego ułamka, a nie stałej liczby - nie można tak wyraźnie zmniejszyć problemu, ponieważ wymaga to obliczenia 5 median, każda na liście $następnie$ rekurencji na liście o długości co najwyżej ${\ Displaystyle {\ Frac {7} {10}} n}$ . Podobnie jak w przypadku grupowania przez 3, poszczególne listy są krótsze, ale całkowita długość nie jest krótsza – w rzeczywistości dłuższa – i dlatego można udowodnić tylko granice superliniowe. Grupowanie w kwadrat $skomplikowane$ o długości $jest$ .

Blum, M .; Floyd, RW ; Pratt, VR ; Rivest, RL ; Tarjan, RE (sierpień 1973). „Granice czasowe dla wyboru” (PDF) . Journal of Computer and System Sciences . 7 (4): 448–461. doi : 10.1016/S0022-0000(73)80033-9 .

Linki zewnętrzne

„ Notatki z wykładu z 30 stycznia 1996 r.: Wybór deterministyczny ”, ICS 161: Projektowanie i analiza algorytmów, David Eppstein