Рубрики

ВОРОТА | GATE-CS-2009 | Вопрос 39

В быстрой сортировке для сортировки по n элементам (n / 4) -й наименьший элемент выбирается как сводный, используя алгоритм времени O (n). Какова временная сложность быстрой сортировки в худшем случае?
<Предварительно>
(А) (П)
(В) (NlogN)
(С) (П ^ 2)
(D) (n ^ 2 log n) </ pre>

(А) А
(Б) Б
(С) С
(D) D

Ответ: (Б)
Объяснение: Ответ (B)
Выражение рекурсии становится:

T (n) = T (n / 4) + T (3n / 4) + cn

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

ВОРОТА | GATE-CS-2009 | Вопрос 39

0.00 (0%) 0 votes