2004-gre-cs-practice-book.pdf/Q03

Ссылки сюда (1) →

Вопрос: Q03-4c9f66

Какой из следующих алгоритмов имеет время выполнения O(n²) в наихудшем случае, но O(n×log(n)) в среднем?

Ответы

• Пузырьковая сортировка
• Сортировка слиянием
• Пирамидальная сортировка (сортировка кучей)
• Правильный ответ: Быстрая сортировка
• Турнирная (Tournament) сортировка

Объяснение

Исходники — вопрос 3 на 13 странице книги «2004-gre-cs-practice-book.pdf»

• Quicksort да, в худшем — квадрат, в среднем — O(n×log(n))
• Сортировка слиянием — имеет O(n log n) в худшем и среднем (но помните, ест O(n) памяти)
• Пирамидальная сортировка — в среднем и худшем O(n log n) (но есть другие проблемы).
• Пузырьковая — квадрат в худшем и среднем.
• Турнирная сортировка — имеет O(n log n) в худшем и среднем.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.