Czy możliwe jest obliczenie mediany listy liczb lepszej niż O (n log n)?
Wiem, że możliwe jest obliczenie średniej z listy liczb w O (n). Ale co z medianą? Czy istnieje lepszy algorytm niż sortowanie (O (n log n)) i szukanie środkowego elementu (lub średniej z dwóch środkowych elementów, jeśli parzysta liczba pozycji na liście)?