ВОРОТА | 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

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

• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
• ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65