Рубрики

ВОРОТА | GATE-CS-2001 | Вопрос 14

Рандомизированная быстрая сортировка — это расширение быстрой сортировки, в которой стержень выбирается случайным образом. Какова сложность наихудшего случая сортировки n чисел с помощью рандомизированной быстрой сортировки?
(A) O (n)
(B) O (n Log n)
(С) O (n 2 )
(D) O (n!)

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

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

ВОРОТА | GATE-CS-2001 | Вопрос 14

0.00 (0%) 0 votes