Рубрики

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

Самая тесная нижняя граница для числа сравнений, в худшем случае для сортировки на основе сравнения, имеет порядок
(А) Н
(Б) Н ^ 2
(С) NlogN
(D) N (logN) ^ 2

Ответ: (с)
Объяснение: Количество сравнений, которое требует алгоритм сортировки сравнений, увеличивается пропорционально Nlog (N), где N — количество элементов для сортировки. Эта граница асимптотически тесна:

Учитывая список различных чисел (мы можем предположить это, потому что это анализ наихудшего случая), есть N факторных перестановок, точно одна из которых является списком в отсортированном порядке. Алгоритм сортировки должен получить достаточно информации из сравнений, чтобы определить правильные перестановки. Если алгоритм всегда завершается после не более чем f (N) шагов, он не может различить более 2 ^ f (N) случаев, потому что ключи различны и каждое сравнение имеет только два возможных результата. Следовательно,

2 ^ f (N)> = N! или эквивалентно f (N)> = log (N!).
Поскольку log (N!) — Omega (NlogN), ответ — NlogN.
Подробнее читайте здесь

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

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

0.00 (0%) 0 votes