Оглавление
Быстрый выбор
-
Основы быстрого выбора
- Алгоритм быстрого выбора используется для поиска k-го наименьшего элемента в неупорядоченном списке.
- Разработан Тони Хоаром и известен как алгоритм выбора Хоара.
- Эффективен в среднем случае, но имеет низкую производительность в худшем случае.
-
Реализация и сложность
- Быстрый выбор использует рекурсию только в сторону с искомым элементом, что снижает среднюю сложность до O(n).
- Обычно реализуется как алгоритм на месте и частично сортирует данные.
-
Разбиение списка
- Используется схема разбиения Lomuto для группировки списка на две части.
- При быстрой сортировке рекурсивно сортируются обе ветви, что обеспечивает лучшую производительность.
-
Сравнение с быстрой сортировкой
- Быстрый выбор является частичной быстрой сортировкой, которая генерирует только O(log n) из O(n) перегородок.
- Имеет линейную производительность и требует постоянных затрат памяти.
-
Влияние выбора опорной точки
- Выбор хороших опорных точек приводит к экспоненциальному уменьшению размера набора поиска и линейной производительности.
- Неправильный выбор опорных точек может привести к квадратичной производительности в худшем случае.
-
Варианты и оптимизация
- Можно использовать случайный разворот для почти линейного времени работы.
- Существуют стратегии разворота, такие как медиана из 3, которые обеспечивают линейную производительность.
- Алгоритм median of medians обеспечивает линейную производительность в худшем случае, но требует высоких затрат на вычисления.
- Комбинация базового быстрого выбора с медианой медиан может обеспечить как быструю среднюю производительность, так и линейную в худшем случае.
-
Дополнительные сведения
- Существуют точные вычисления средней временной сложности для различных стратегий разворота.
- Алгоритм Флойда-Ривеста обеспечивает среднюю сложность 1.5n + O(n1/2) для медианы.
- Ссылки на другие алгоритмы и реализации быстрого выбора приведены в конце статьи.