Rozważmy następujący problem:
Dany jest zbiór \( A \) składający się z \( n \) liczb oraz liczba \( k \). Należy wyznaczyć \( k \)-ty co do wielkości element zbioru \( A, \) tzn. takie \( a\in A \), że \( |\{ x\in A : x < a \}|=k-1 \).
Dla niektórych wartości \( k \) (np. 1 lub n) problem jest bardzo prosty i wymaga jedynie wyznaczenia minimalnej lub maksymalnej wartości w A, co możemy zrobić w czasie \( O(n) \). Znacznie ciekawszym problemem jest np. znajdowanie mediany, czyli \( \lfloor \frac{n}{2} \rfloor \)-tego co do wielkości elementu. Tu niestety problem jest bardziej skomplikowany.
Możemy zauważyć, że szybkie (np. o złożoności \( O(n) \)) znajdowanie mediany pozwoliłoby tak poprawić algorytm sortowania QuickSort, żeby nawet w pesymistycznym przypadku działał w czasie \( O(n\log n) \).
Najprostszym rozwiązaniem naszego problemu może być uporządkowanie zbioru, np. algorytmem MergeSort, i wskazanie k-tego elementu. Takie postępowanie wymaga czasu \( \Omega(n\log n) \).
Jednak można łatwo zauważyć, że nasz problem jest znacznie prostszy od problemu sortowania. Czy można rozwiązać go szybciej? Okazuje się, że jest to możliwe. W następnej części wykładu przedstawimy dwa algorytmy, które rozwiązują nasz problem znacznie sprytniej.