Рубрики

ВОРОТА | GATE-CS-2015 (Mock Test) | Вопрос 9

Какие из следующих изменений типичной QuickSort улучшают ее производительность в среднем и обычно выполняются на практике.

1) Randomly picking up to make worst case less 
   likely to occur.
2) Calling insertion sort for small sized arrays 
   to reduce recursive calls.
3) QuickSort is tail recursive, so tail call 
   optimizations can be done.
4) A linear time median searching algorithm is used 
   to pick the median, so that the worst case time 
   reduces to O(nLogn)

(А) 1 и 2
(Б) 2, 3 и 4
(С) 1, 2 и 3
(D) 2, 3 и 4

Ответ: (с)
Объяснение: Четвертая оптимизация обычно не используется, она уменьшает сложность времени наихудшего случая до O (nLogn), но скрытые константы очень высоки.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2015 (Mock Test) | Вопрос 9

0.00 (0%) 0 votes