Алгоритми та структури даних · Senior · Запитання 16 з 75
Яка середня складність quickselect для пошуку k-го найменшого елемента?
- 1O(log n)
- 2O(n log n)
- ✓Правильна відповідь: O(n)
Пояснення
Як і quicksort, він робить розбиття, але рекурсивно йде лише в ту частину, що містить позицію k, тож робота n + n/2 + n/4 + ... ≈ 2n. Найгірший випадок O(n²); медіана медіан гарантує O(n) з більшою константою.