Алгоритми та структури даних · Senior · Запитання 58 з 75
Чому глибина рекурсії quicksort - проблема і як її обмежують?
- ✓Правильна відповідь: Погані опорні дають глибину n; рекурсія йде в меншу частину
- 2Глибока рекурсія робить сортування нестабільним для рівних ключів
- 3Глибина завжди log n, тож проблеми немає
Пояснення
Рекурсія в меншу частину й цикл по більшій гарантують глибину стека O(log n), навіть коли час деградує. Introsort також обмежує глибину й переходить на heapsort.