Algorytmy i struktury danych · Senior · Pytanie 16 z 75
Jaka jest średnia złożoność quickselect przy szukaniu k-tego najmniejszego elementu?
- 1O(log n)
- 2O(n log n)
- ✓Poprawna odpowiedź: O(n)
Wyjaśnienie
Jak quicksort dzieli tablicę, ale rekurencyjnie schodzi tylko do części zawierającej pozycję k, więc praca to n + n/2 + n/4 + ... ≈ 2n. Najgorszy przypadek to O(n²); mediana median gwarantuje O(n) z większą stałą.