Median of Medians

Question

Przeczytałem statystyki zleceń, aby znaleźć k-ty najmniejszy (lub największy) element w tablicy o rozmiarze n w czasie liniowym O (n).

Jest jeden krok, który musi znaleźć medianę median.

1. Podziel macierz na [n/5] części. Każda część ma 5 elementów.
2. Znajdź medianę w każdej części. (Mamy teraz numery [n/5])
3. Powtarzaj kroki 1 i 2, dopóki nie będziemy mieli tylko ostatniego numeru. (Tj rekurencyjne)

T (n) = T (N/5) + O (n) i można otrzymać T (n) = O (n).

Ale czy to prawda, że ​​liczba, którą w końcu uzyskaliśmy, nie jest medianą median, ale medianą median mediany median mediany median, jeśli mamy szeroki wachlarz.

Proszę wziąć pod uwagę tablicę zawierającą 125 elementów.

Po pierwsze, dzieli się na 25 części i znajdujemy 25 median. Następnie dzielimy te 25 liczb na 5 części i znajdujemy 5 median, Wreszcie uzyskamy liczbę, która jest medianą mediany median. (Nie mediana median)

Powodem, dla którego się o to troszczę, jest to, że rozumiem, że jest co najwyżej około [3/4] * n elementów, które są mniejsze (lub większe) niż mediana median. Ale co, jeśli nie jest to mediana median, ale mediana median median? W gorszym przypadku musi być mniej elementów, które są mniejsze (lub większe) niż czop, co oznacza, że ​​czop jest bliżej granicy macierzy.

Jeśli mamy BARDZO duży zbiór, i znaleźliśmy jego medianę median median z median median. W najgorszym przypadku oś obrotowa, którą znaleźliśmy, wciąż może być bardzo bliska granicy i jaka jest w tym przypadku złożoność czasu?

Zrobiłem zestaw danych z 125 elementów. Czy wynik 9?

0.8 0.9 1 inf inf 
1.8 1.9 2 inf inf 
6.8 6.9 7 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

2.8 2.9 3 inf inf 
3.8 3.9 4 inf inf 
7.8 7.9 8 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

4.8 4.9 5 inf inf 
5.8 5.9 6 inf inf 
8.8 8.9 9 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

gdzie inf oznacza, że ​​liczba jest wystarczająco duża.

Answer 1

Oznaczmy twoją medianę median median z ... jako [medianę] * = M.

Po pierwsze, uważam, że mediana algorytmu median (aby wybrać dobry pivot) nie jest rekursywna. Algorytm jest następujący:

1. Podział elementów w 5 grupach
2. Znajdź medianę każdej grupy
3. Znajdź medianę median i używać go jako pivot.

Mediana mediana będzie mniejsza niż 3n/10 elementów i większa niż inne 3n/10 elementów, a nie 3n/4. Po wybraniu median masz numery n/5. Mediana mediana jest większa/mniejsza niż połowa z tych liczb, która wynosi n/10. Każda z tych liczb jest medianą, więc jest większa/mniejsza niż 2 cyfry, dając kolejne 2n/10 liczb. Teraz w sumie otrzymujesz n/10 + 2n/10 = 3n/10 liczb.

Aby rozwiązać swoje drugie pytanie, po zebraniu grupy 5 w swoim przykładzie zbioru danych i obliczania ich median, będziemy mieć następującą sekwencję:

1, 2, 7, inf, inf 
3, 4, 8, inf, inf 
5, 6, 9, inf, inf, 
inf, inf, inf, inf, inf, 
inf, inf, inf, inf, inf. 

Więc mediana median będzie faktycznie 9.

proponowanego [mediana] * Czas pracy algorytmu będą:

T(n) = O(n * log(n)) 

teraz spróbujmy przeanalizować ile liczb mamy mniejszy/większy niż M. mamy następujące grupy:

• głębokości 1: N/5 wszystkich elementów środkowych
• głębokość 2 N/25 wszystkie elementy median
• ...
• głębokość wzorze I: n/(5^i) wszystkie elementy median

Każda grupa jest mniejsza/większa niż 2 elementy poprzedniego głębokość, która jest mniejsza/większa niż 2 elementy poprzedniego głębokości, i tak dalej:

Łącznie obliczamy, że nasz M jest większy/mniejszy niż (n * (2^k) + k * n)/((2^k) * (5^k)). Dla głębokości = 1 dostajesz medianę median, czyli 3n/10.

Teraz zakładając, że głębokość jest [log_5 (n)], czyli n = 5^k, otrzymujemy:

5^k * (k + 2^k)/(5^k * 2^k), który jest -> 1.