Предположим, у нас есть 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
0.00 (0%) 0 votes