Алгоритми та структури даних · Senior · Запитання 68 з 75
Що дає quicksort рандомізація?
- 1Стабільність для елементів із рівними ключами
- ✓Правильна відповідь: Очікуване O(n log n) для будь-яких даних
- 3Гарантоване O(n log n) у найгіршому разі
Пояснення
З випадковим опорним жоден фіксований вхід не буде стабільно поганим, тож очікування справджується для будь-яких даних, зокрема ворожих. Найгірший випадок усе ще можливий, просто вкрай малоймовірний.