Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 52

Предположим, у нас есть O (n) алгоритм времени, который находит медиану несортированного массива.

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

Ответ: (D)
Объяснение:

Если мы выберем медиану в качестве основного элемента, то после алгоритма разбиения он перейдет в середину массива с половиной элементов слева и половиной справа.
Таким образом, после алгоритма разбиения массив будет разделен на две равные части по n / 2 элементов каждая.
Следовательно, результирующее рекуррентное соотношение будет
T (n) = O (n) (для выбора медианы) + O (n) (для разбиения) + T (n / 2) + T (n / 2)
T (n) = O (n) + 2T (n / 2)
Мы можем решить вышеупомянутое рекуррентное отношение, используя метод master

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

ВОРОТА | GATE-CS-2006 | Вопрос 52

0.00 (0%) 0 votes