Dlaczego algorytm median-median nie może używać bloku wielkości 3?

Question

Analizuję deterministyczną medianę przy założeniu, że dane wejściowe są podzielone na 3 części zamiast 5, a pytanie brzmi: Gdzie się rozkłada?

deterministyczny mediana znalezienie Algorytm:

SELECT (i, n)

1. podzielić N elementów na grupy 5. znaleźć medianę każdej grupie 5 elementu z pamięci.

2. Rekurencyjnie WYBIERZ medianę x median grupy ⎣n/5⎦ jako oś obrotu.

3. Partycja wokół osi x. Niech K = pozycja (x)

4.if I = k, wtedy powrót x

ten blok i < K

następnie rekurencyjnie SELECT-tego najmniejszy element dolnej części

jeszcze rekursywnie WYBIERZ (i-k) th najmniejszy element w górnej części

Przeszedłem przez odbyt Ysis algorytmu i wierzę, że Krok 1 i 3 zajmą O (n), gdzie zajmuje tylko stały czas, aby znaleźć medianę 5 elementów, a Krok 2 zajmuje T (n/5) .so co najmniej 3/10 elementów są ≤ p, a co najmniej 3/10 macierzy jest ≥ p, dlatego też krok 4 będzie T (7n/10) i otrzyma nawrót. T (n) ≤ cn + T (n/5) + T (7n/10), , ale kiedy podzielę elementy w grupie 3, powiedzmy 9 elementów i podzielę je w grupie tak, aby:

{1,2,10} {4,11,14}, {15,20,22}

Mam mediany 2,11,20 i p = 11.

ogólnie w grupie pięciu powiedzmy g = n/5 grup i co najmniej ⌈g/2⌉ z nich (te grupy, których mediana to ≤ p) co najmniej trzy z pięciu elementów to ≤ p. więc całkowita liczba elementów ≤ p wynosi co najmniej 3⌈g/2⌉ ≥ 3n/10. ALE w grupie 3 możemy uzyskać wszystkie trzy elementy mogą być MNIEJSZE niż p. i tutaj myślę, że algorytm się zepsuje !!

Czy otrzymałem prawidłowy pomysł?

Answer 1

W grupie 3, podobnie jak w przypadku grup 5, około połowa grup będzie miała medianę mniejszą niż mediana median, więc w tych grupach można odrzucić elementy mniejsze niż ich mediana. W twoim przypadku (1,2,10) ma medianę mniejszą niż 11, więc możesz odrzucić 1 i 2.

Tam, gdzie myślę, że wszystko załamuje się dla grup 3 jest w kosztach. 3 (podłoga (piętro (n/5)/2 - 2), która wynosi w przybliżeniu 3n/10 staje się 2 (podłoga (piętro (n/3)/2 -2) lub tak, czyli mniej więcej n/3. Oznacza to, że 7n/10 staje się 2n/3. Podłoga (n/5) staje się podłogą (n/3), więc zamiast 7cn/10 + 2cn/10 = 9cn/10 otrzymasz tylko 2cn/3 + cn/3 = cn, a zamiast T (n) < = cn będziesz mieć coś, w czym będziesz musiał dokładnie przyjrzeć się warunkom, które nie obejmują c, i może się okazać, że to nie jest liniowe.

Wygląda na to, że faktycznie można wyrzucić nieco więcej elementów na każdym etapie rekursji, ale rekursja dzieli ilość pracy pozostawioną przez 3, a nie 5, a to nie wystarcza, aby równać się.