W algorytmie median-of-medians, musimy podzielić tablicę na kawałki wielkości 5. Zastanawiam się, jak wynalazcy algorytmów wymyślili magiczna liczba "5", a nie, może być, 7 lub 9 lub coś innego?Mediana algorytmu median: dlaczego dzielić tablicę na bloki wielkości 5
myślę, że jeśli będziesz sprawdzać „Dowód O (n) Czas trwania” sekcji strony wiki dla medians-of-medians algorithm:
Mediana-obliczania wywołanie rekurencyjne nie przekracza najgorszego scenariusza zachowań liniowy ponieważ lista środkowych 20% wielkości listy, a drugi wywołanie rekurencyjne recurses na co najwyżej 70% z listy, co czas przepływu
o (n) Określenie Cn do prac partycjonujących (odwiedziliśmy każdy element a con wiele razy, aby uformować je w grupy n/5 i przyjąć każdą medianę w czasie O (1)). Z tego, za pomocą indukcji, można łatwo wykazać, że
To powinno pomóc zrozumieć, dlaczego.
Liczba musi być większa niż 3 (i oczywiście liczba nieparzysta) dla algorytmu. 5 jest najmniejszą liczbą nieparzystą większą niż 3. Tak więc 5 zostało wybrane.
Nie musi być większa tan 3 (i nieparzysta), zobacz moją odpowiedź poniżej. –
Tak, ale to jest inny algorytm. Jest tylko niewielka zmiana algorytmu, o który pytał OP - ale wciąż jest to inny algorytm. OP zapytał "dlaczego w tym konkretnym algorytmie potrzebujemy bloków 5", a nie "jest wariant na tym algorytmie, w którym moglibyśmy użyć mniejszych bloków". Próbowali zrozumieć, jak coś zostało obliczone, zamiast próbować znaleźć, czy jest coś innego, co może zrobić to lepiej. – rabensky
Można również użyć bloków o wielkości 3 lub 4, jak pokazano w artykule Select with groups of 3 or 4 K. Chen i A. Dumitrescu (2015). Chodzi o to, aby dwa razy użyć algorytmu "mediana median", a dopiero potem partycji. Zmniejsza to jakość czopu, ale jest szybszy.
Więc zamiast:
T(n) <= T(n/3) + T(2n/3) + O(n)
T(n) = O(nlogn)
dostaje:
T(n) <= T(n/9) + T(7n/9) + O(n)
T(n) = Theta(n)
Dowodzi to O (n) Czas trwania zastosowania 20%, to nie ma obalić O (n) Czas pracy jakiejś innej wartości procentowej (jeśli jakiś inny procent był również O (n), nie uzasadnia wyboru 20% powyżej drugiego). – Dukeling