🔥 Quickselect быстрый, пока не выберет плохой pivot
Обычный Quickselect в среднем работает за O(n), но неудачный выбор опорного элемента может превратить поиск k-го элемента в O(n²).
В 1973 году Блум, Флойд, Пратт, Ривест и Тарьян предложили алгоритм median of medians, который гарантирует линейное время даже в худшем случае.
Идея:
1. Разделить массив на группы по 5 элементов.
2. Найти медиану каждой группы.
3. Рекурсивно найти медиану полученных медиан.
4. Использовать её как pivot для Quickselect.
int mom_pivot(int *arr, int n)
{
if (n <= 5) {
sort(arr, n);
return arr[n / 2];
}
int medians[(n + 4) / 5];
for (int i = 0; i < n; i += 5) {
int len = (n - i < 5) ? n - i : 5;
sort(arr + i, len);
medians[i / 5] = arr[i + len / 2];
}
return mom_pivot(medians, (n + 4) / 5);
}
Такой pivot не обязательно будет настоящей медианой массива, но он гарантированно не окажется слишком близко к краю. После разбиения отбрасывается достаточно большая часть элементов, поэтому рекурсия не деградирует.
Итоговая сложность поиска:
Средний случай: O(n)
Худший случай: O(n)
Дополнительная память: зависит от реализации
На практике randomized Quickselect часто быстрее из-за меньших констант. Median of medians нужен там, где важна строгая гарантия времени: real-time системы, adversarial input и библиотеки с предсказуемой производительностью.
Обычный Quickselect в среднем работает за O(n), но неудачный выбор опорного элемента может превратить поиск k-го элемента в O(n²).
В 1973 году Блум, Флойд, Пратт, Ривест и Тарьян предложили алгоритм median of medians, который гарантирует линейное время даже в худшем случае.
Идея:
1. Разделить массив на группы по 5 элементов.
2. Найти медиану каждой группы.
3. Рекурсивно найти медиану полученных медиан.
4. Использовать её как pivot для Quickselect.
int mom_pivot(int *arr, int n)
{
if (n <= 5) {
sort(arr, n);
return arr[n / 2];
}
int medians[(n + 4) / 5];
for (int i = 0; i < n; i += 5) {
int len = (n - i < 5) ? n - i : 5;
sort(arr + i, len);
medians[i / 5] = arr[i + len / 2];
}
return mom_pivot(medians, (n + 4) / 5);
}
Такой pivot не обязательно будет настоящей медианой массива, но он гарантированно не окажется слишком близко к краю. После разбиения отбрасывается достаточно большая часть элементов, поэтому рекурсия не деградирует.
Итоговая сложность поиска:
Средний случай: O(n)
Худший случай: O(n)
Дополнительная память: зависит от реализации
На практике randomized Quickselect часто быстрее из-за меньших констант. Median of medians нужен там, где важна строгая гарантия времени: real-time системы, adversarial input и библиотеки с предсказуемой производительностью.