Конспект: выбор k-го элемента

Понятия

k-я порядковая статистика - элемент на позиции k в отсортированном порядке (с 1): k = 1 - минимум, k = n - максимум, ≈ n/2 - медиана. Задача ВЫБОРА - найти её, не сортируя весь массив. Помни индексацию: k-я статистика - это a[k−1].

Медиана - серединный по позиции элемент; устойчивее среднего к выбросам (зависит от ПОЗИЦИИ, а не от величины). Перцентили (95-й, 99-й) - статистики с номерами 0.95n, 0.99n.

Наивное решение - полная сортировка за Θ(n·log n) и a[k−1]. Верно, но избыточно: платим за порядок ВСЕХ ради одного элемента. Ещё наивнее - k раз найти минимум: Θ(k·n), для медианы Θ(n²).

Quickselect - разбиение (как в быстрой сортировке) + спуск в ОДНУ сторону: опорный встаёт на ранг p; k == p - ответ, k < p - влево, k > p - вправо. Одна ветка вместо двух: T(n) = T(n/2) + Θ(n), работа n + n/2 + n/4 + … = 2n = Θ(n) в среднем. Работает на месте, попутно даёт разбиение вокруг ответа (готовый топ-k).

Худший случай quickselect - Θ(n²): плохой опорный (почти крайний) отрезает по одному, размеры n, n−1, …, 1. Классика - отсортированный вход + опорный-последний.

Рандомизация опорного - случайный выбор: ожидаемо Θ(n) на ЛЮБОМ входе. Источник неудачи переносится с данных (контролирует чужой) на монетку (контролируешь ты); худший случай нельзя подстроить. Первый пример РАНДОМИЗИРОВАННОГО алгоритма.

Медиана медиан (BFPRT) - Θ(n) ГАРАНТИРОВАННО, без случайности. Группы по 5 → медиана каждой → рекурсивно медиана медиан = опорный. Отсекает ≥ 3n/10 с каждой стороны, спуск по ≤ 7n/10. T(n) ≤ T(n/5) + T(7n/10) + Θ(n), линия из 1/5 + 7/10 = 9/10 < 1. Плата - большая константа.

Что унести

Чтобы узнать элемент нужного РАНГА, не нужен порядок всех остальных - вот стержень главы.

Практический вывод: бери встроенное (numpy.partition, std::nth_element) - там рандомизированный выбор (иногда с переключением на медиану медиан). Рандомизация - общий приём: детерминированный алгоритм уязвим к подстроенному входу → добавь случайность внутрь, и «неудача» перестанет зависеть от того, кто подсовывает данные. А медиана медиан - образец того, как теория берёт ЖЕЛЕЗНУЮ гарантию там, где практика довольствуется ожиданием.

Ловушки джокера

Спустился в ОБЕ стороны (как в быстрой сортировке). Получил Θ(n·log n) - весь смысл выбора потерян. Иди строго в одну - по сравнению k с p.

Промах на один в индексации. k-я статистика (с 1) - это a[k−1] (с 0). Самая частая ошибка.

Фиксированный опорный в проде. На отсортированных/почти отсортированных данных (они повсюду) - Θ(n²), а злоумышленник сделает это нарочно. Бери случайный.

Спутал «ожидаемо Θ(n)» с «гарантированно Θ(n)». Рандомизация даёт ОЖИДАНИЕ; гарантию в худшем случае - только медиана медиан.

Группы по 3 в медиане медиан «чтобы дешевле». Сумма долей станет ровно 1, алгоритм скатится к Θ(n·log n).

Искал медиану медиан сортировкой всех n/5 медиан. Это Θ(n·log n) уже на первом шаге - мимо линии. Её находят тем же выбором рекурсивно.

Проверь себя

Что такое k-я порядковая статистика и почему медиана устойчивее среднего?

Почему полная сортировка ради одного элемента - перебор?

Чем quickselect отличается от быстрой сортировки и откуда его средняя Θ(n)?

Откуда у quickselect худший случай Θ(n²) и как его лечит рандомизация?

Как медиана медиан гарантирует линию и почему группы именно по 5?