Witam Próbuję zrozumieć, w jaki sposób medianadziała algorytm median. We wszystkich przykładach, które do tej pory widziałem, istnieją już grupy podzielonych liczb, zanim rozpocznie się wykonywanie algorytmu, więc nie mogę zrozumieć, w jaki sposób te grupy są tworzone. że jest 9 grup po 5 liczb, na przykład 45 liczb, lub 4 grupy po 10 liczb, w sumie 40 liczb, więc co, jeśli mamy n liczb ..? Czy jest jakaś dobra technika, którą powinienem zastosować, aby znaleźć liczba elementów, które powinna mieć jego grupa?
Odpowiedzi:
1 dla odpowiedzi № 1MoM to algorytm rekurencyjny. Istnieje jako dobry sposób na wybranie „pivot” dla algorytmu takiego jak quicksort lub quickselect. Dlatego musi działać w określonych ramach czasowych.
Może być łatwiejsze do zrozumienia, jeśli zostanie wyjaśnione jako przypadek podstawowy i przypadek rekurencyjny.
Podstawa jest wystarczająco przejrzysta. Jeśli masz mniej niż pięć elementów na liście, mediana jest naiwna.
Ale jeśli twoja lista ma co najmniej pięć elementów, tymoże zastosować przypadek rekurencyjny. Zamierzasz wziąć kolejne grupy pięciu elementów z twojej dużej listy, znaleźć ich medianę i dodać ją do mniejszej listy. (Jeśli masz jeszcze trochę, możesz je zignorować.)
Jeśli ta nowa, mniejsza lista jest wystarczająco mała, tymoże zastosować podstawkę, jak opisano powyżej. W przeciwnym razie przejdziesz przez „małą” listę, aby utworzyć kolejną, jeszcze mniejszą listę. Pij, spłukuj i powtarzaj, aż pozostanie mniej niż pięć pozostałych elementów. Działa to z dowolnym rozmiarem listy.
Jak duży powinien być „pięć”? Okazuje się, że 5 jest optymalne. Ktoś pokazał analizę złożoności na stronie Wikipedii dla tego tematu. Zasadniczo większe wartości „pięciu” dają lepsze przybliżenie mediany kosztem większej pracy, aby znaleźć medianę „pięciu”. Niestety 3 nie zmniejsza przestrzeni wyszukiwania wystarczającej na iterację, aby był wart wyboru „pięć”. I na ogół musi być dziwne, chyba że chcesz spędzić cykle dzieląc różnicę między elementami.