Chciałbym wiedzieć, czy istnieje algorytmznaleźć medianę nieparzystej długości. Oczywiście można po prostu posortować tablicę i wziąć środek, ale najlepiej, gdy interesuje ją tylko mediana, można uzyskać zyski pod względem złożoności czasowej algorytmu.
Jeśli taki algorytm nie istnieje, wszelkie sugestie dotyczące sposobu opracowania takiego algorytmu będą świetne.
Dzięki
Odpowiedzi:
0 dla odpowiedzi № 1Jest to rozwiązywane przez a algorytm wyborui można to zrobić w O(n) czas. Szybki wybórlub udoskonalenie introselect, są popularnymi metodami.
Zostaje uruchomione bardzo krótkie podsumowanie quickselectquicksort, ale zamiast sortowania obu połówek na każdym kroku, sortujesz tylko połowę zawierającą szukany element, który można określić, licząc ile elementów znajduje się w każdej partycji.
C ++, na przykład, ma to jako standardową funkcję biblioteczną: n__element.
0 dla odpowiedzi nr 2
Możesz użyć Algorytm wyboru która może znaleźć kth najmniejszy element tablicy z k jest połową wielkości tablicy.
W przypadku danych nieustrukturyzowanych znajduje się w nim O(n).
Ale zawsze pamiętaj, że teoretyczna złożoność to nie wszystko!
Czytaj także to pytanie.
0 dla odpowiedzi № 3
Tak, istnieje algorytm. Problem, o którym mówisz, polega na znalezieniu ktegogo największego elementu, gdzie k jest wartością połowy + 1 długości tablicy. Oto link do sposobu, aby zrobić to w czasie O (n), Mediana median.