Рубрики

Алгоритмы | Сортировка | Вопрос 18

Рассмотрим алгоритм быстрой сортировки. Предположим, что существует процедура поиска сводного элемента, который разбивает список на два подсписка, каждый из которых содержит не менее одной пятой элементов. Пусть T (n) будет количеством сравнений, необходимых для сортировки n элементов. потом
(A) T (n) <= 2T (n / 5) + n
(B) T (n) <= T (n / 5) + T (4n / 5) + n
(C) T (n) <= 2T (4n / 5) + n
(D) T (n) <= 2T (n / 2) + n

Ответ: (Б)
Пояснение: Для случая, когда n / 5 элементов находятся в одном подмножестве, T (n / 5) сравнения необходимы для первого подмножества с n / 5 элементами, T (4n / 5) для остальных 4n / 5 элементов, и n для нахождения оси.

Если в одном наборе более n / 5 элементов, то в другом наборе будет менее 4n / 5 элементов, а временная сложность будет меньше T (n / 5) + T (4n / 5) + n, поскольку дерево рекурсии будет более сбалансированный.
Тест на этот вопрос

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

Алгоритмы | Сортировка | Вопрос 18

0.00 (0%) 0 votes