🔥 Quickselect быстрый, пока не выберет плохой pivot — 3 августа 2026 г. в 13:22:37.975
🔥 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 и библиотеки с предсказуемой производительностью.