Медиана медиан: линейное время в худшем случае

Если ты понимаешь, как медиана медиан гарантирует опорный, отсекающий ≥3n/10 с каждой стороны, почему группы именно по 5 и откуда линия из T(n) ≤ T(n/5)+T(7n/10)+Θ(n), листай до «Теперь сам».

Как думаешь, можно ли выбрать опорный так, чтобы худшего случая не было вовсе

Рандомизация из прошлого урока даёт линию в ОЖИДАНИИ, но теоретически может не повезти - монетка ляжет плохо, и получишь квадрат (пусть и с исчезающе малой вероятностью). А что, если нужна ЖЕЛЕЗНАЯ гарантия Θ(n) при любом входе и без всякой удачи? Проблема ясна: плохой опорный - это почти крайний элемент. Значит нужен способ БЫСТРО находить опорный, про который заранее известно, что он не слишком близко к краю - что по обе стороны от него лежит существенная доля массива. Причём находить его надо дёшево, за линию, иначе смысла нет. Кажется, что это замкнутый круг (чтобы найти хороший опорный, надо почти найти медиану), но выход есть - через рекурсию по уменьшенной задаче.

На что это похоже

Выборы делегата от большого собрания через двухступенчатую систему. Всех рассаживают за столики по пять человек. Каждый столик выдвигает своего СРЕДНЕГО по некоторому признаку - не самого крайнего, а серединного. Потом из этих выдвиженцев (их впятеро меньше) тем же способом выбирают одного главного. Такой главный гарантированно не радикал: он серединный среди серединных, и по обе стороны от него - большие группы людей. Медиана медиан - ровно эта двухступенчатая фильтрация: столики по пять, их медианы, медиана медиан. Итоговый опорный «умеренный» по построению, и потому делит массив надёжно, а не как повезёт.

Механизм: группы по пять, медиана их медиан

выбор_МоМ(a, k):
    если |a| ≤ 5:  вернуть k-й через сортировку     # база: мелочь сортируем прямо
    1. разбить a на группы по 5 (последняя, может, короче)
    2. в каждой группе найти медиану (сортировкой пятёрки - это O(1) на группу)
    3. собрать медианы групп → массив M (их ≈ n/5)
    4. опорный = выбор_МоМ(M, середина M)            # РЕКУРСИЯ: медиана медиан
    5. разбить a вокруг этого опорного, пусть он встал на позицию p
    6. как в quickselect: k==p → ответ; k<p → влево; k>p → вправо (РЕКУРСИЯ по a)

Здесь ДВЕ рекурсии, и это не описка. Шаг 4 - рекурсия на массиве вчетверо-впятеро меньшем (n/5 медиан), чтобы найти хороший опорный. Шаг 6 - обычный спуск quickselect в одну сторону, но теперь по массиву размером не больше 7n/10 (это докажем ниже). Сумма двух уменьшенных задач и линейной работы на разбиение и даёт линию.

Правило

Медиана медиан (BFPRT) находит k-ю статистику за Θ(n) в ХУДШЕМ случае. Опорный выбирается детерминированно: группы по 5 → медиана каждой → рекурсивно медиана этих медиан. Такой опорный гарантирует, что с каждой стороны отсечётся не меньше ≈ 3n/10, поэтому рекурсивный участок ≤ 7n/10. Отсюда T(n) ≤ T(n/5) + T(7n/10) + Θ(n), и раз 1/5 + 7/10 = 9/10 < 1, время линейно. Плата за гарантию - большая константа: на практике чаще берут рандомизированный выбор, а медиану медиан - когда худший случай недопустим.

Разбор: откуда берётся отсечение 3n/10

Это сердце доказательства. Пусть групп n/5, у каждой есть медиана, и M - медиана этих медиан. Раз M - медиана среди n/5 групповых медиан, то ПОЛОВИНА из них, то есть n/10 медиан, не меньше M. Возьмём любую такую группу (её медиана ≥ M): в группе из 5 элементов медиана - третий по величине, значит в группе есть ещё как минимум ДВА элемента, не меньших своей медианы, а та не меньше M. Итого в каждой такой группе не меньше ТРЁХ элементов ≥ M. Групп таких n/10, по 3 элемента - получаем не меньше 3n/10 элементов во всём массиве, которые ≥ M. Симметрично не меньше 3n/10 элементов ≤ M. Значит, когда мы разобьём массив вокруг M, каждая сторона заберёт не меньше 3n/10 - и рекурсивный спуск пойдёт по участку не больше n − 3n/10 = 7n/10. Вот откуда взялась 7n/10: не «примерно половина» как повезёт, а ГАРАНТИРОВАННЫЕ 7/10 сверху при любом входе. Если n не делится на 10, неполная группа и сама M отнимают несколько элементов: точнее - 7n/10 + 6. На линию эта константа не влияет.

Разбор: почему группы по 5, а не по 3 или по 7

Размер группы подобран так, чтобы сумма долей двух рекурсий была строго меньше единицы - иначе линии не будет. С группами по 5: одна рекурсия на медианах - это T(n/5), вторая - спуск по T(7n/10), сумма долей 1/5 + 7/10 = 9/10 < 1, и линейная работа на уровне не накапливается (геометрически убывает) - итог Θ(n). Проверим тройки: группы по 3 дают медиан n/3, а отсечение всего ≈ 2/6 = n/3 с каждой стороны, значит спуск по 2n/3; рекуррентность T(n/3) + T(2n/3) + Θ(n), а 1/3 + 2/3 = 1 - РОВНО единица, и это уже не линия, а Θ(n·log n): линейная работа повторяется на log n уровнях. Пятёрки - наименьший НЕЧЁТНЫЙ размер, дающий сумму строго меньше единицы (нечётный удобен: у группы есть ровно одна медиана без выбора между двумя средними). Можно и 7, 9 - тоже линия, но константа растёт (сортировать группы дороже). Пятёрка - золотая середина, и потому она в учебниках.

Что ломается без этого

Первая ошибка - взять группы по 3 «чтобы дешевле»: сумма долей станет ровно 1, и алгоритм скатится к Θ(n·log n), потеряв весь смысл (гарантированную линию). Вторая - искать медиану медиан НЕ рекурсивно, а сортировкой всех медиан: сортировка n/5 элементов - это Θ(n·log n) уже на первом шаге, снова мимо линии; медиану медиан надо находить тем же выбором рекурсивно. Третья - забыть, что база (≤ 5 элементов) решается напрямую, и уйти в бесконечную рекурсию на мелочи. Четвёртая - применять медиану медиан там, где хватило бы рандомизации: платить большую константу за гарантию, которая не нужна, - на практике чаще проигрыш по скорости.

Зачем это в работе

Медиана медиан - это теоретический фундамент: она ДОКАЗЫВАЕТ, что выбор k-го элемента (и медианы) решается за Θ(n) в худшем случае, без случайности и без предположений о данных. Практически её берут там, где худший случай недопустим по требованиям (системы реального времени, гарантии задержки, защита от злонамеренного входа без опоры на генератор случайных чисел), и как гарантированный «хороший опорный» внутри других алгоритмов - в частности, интроселекции (аналог introsort для выбора): начать рандомизированным выбором, а при слишком глубокой рекурсии переключиться на медиану медиан, получив и обычную скорость, и гарантию. Идея «построй заведомо неплохой опорный, пожертвовав константой» - образец того, как теория даёт железную гарантию там, где инженерная практика довольствуется ожиданием. Знать оба подхода - рандомизацию (быстро в среднем) и медиану медиан (гарантия) - и понимать, когда какой, - и есть зрелое владение задачей выбора.

Теперь сам

В медиане медиан рекуррентность T(n) ≤ T(n/5) + T(7n/10) + Θ(n). Почему из неё следует Θ(n), а из похожей T(n) = T(n/3) + T(2n/3) + Θ(n) (группы по 3) - уже Θ(n·log n)?