Рубрики

ВОРОТА | GATE-CS-2014- (Set-3) | Вопрос 24

У вас есть массив из n элементов. Предположим, вы реализуете быструю сортировку , всегда выбирая центральный элемент массива в качестве оси. Тогда самая жесткая верхняя граница для худшего случая
(A) O (n 2 )
(B) O (nLogn)
(C) Тета (nLogn)
(D) O (n 3 )

Ответ: (А)
Объяснение: Для любого ввода есть некоторые перестановки, для которых наихудшим случаем будет O (n 2 ) . В некоторых случаях выбор среднего элемента сводит к минимуму шансы встретить O (n 2 ), но в худшем случае он может перейти к O (n 2 ). Какой бы элемент мы не выбрали в качестве Pivot, первый или средний, наихудший случай будет O (n 2 ), поскольку Pivot зафиксирован в позиции. При выборе случайного разворота минимизируются шансы встречи в наихудшем случае, т. Е. O (n 2 ).

См. Эту статью на быстрой сортировке.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2014- (Set-3) | Вопрос 24

0.00 (0%) 0 votes