Худший случай выбора и рандомизация опорного

Если ты понимаешь, откуда у quickselect худший случай Θ(n²), почему случайный выбор опорного даёт ожидаемую Θ(n) на ЛЮБОМ входе и чем это отличается от «среднего по входам», листай до «Теперь сам».

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

В прошлом уроке мы радовались сумме n + n/2 + n/4 + … = 2n. Но она держалась на предположении, что разбиение делит массив ПОПОЛАМ. А что если нет? Возьмём худший вариант: опорный - всегда последний элемент, а массив уже отсортирован по возрастанию. Тогда опорный - максимум участка, слева от него оказываются ВСЕ остальные, а справа - пусто. Разбиение отрезало ровно один элемент, участок укоротился с n до n−1. Следующий шаг - то же самое: n−1 → n−2. Работа идёт n + (n−1) + (n−2) + … + 1 = n(n+1)/2 = Θ(n²) - квадрат, хуже наивной сортировки. Приятная линия оказалась хрупкой: она зависела от удачных опорных. Вопрос - как сделать удачу НАДЁЖНОЙ.

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

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

Механизм: случайный опорный вместо фиксированного

Единственное изменение против прошлого урока - как выбираем опорный. Было: всегда последний (или первый) элемент. Стало: случайный элемент участка, который меняем местами с последним и дальше разбиваем как обычно.

разбить_случайно(a, lo, hi):
    r = случайный индекс в [lo, hi]     # бросок кости
    поменять a[r] и a[hi]               # случайный элемент становится опорным
    вернуть разбить(a, lo, hi)          # дальше - обычное разбиение Ломуто

Всё остальное в quickselect не меняется. Что это даёт: раньше существовал КОНКРЕТНЫЙ вход (отсортированный), на котором фиксированный опорный всегда попадал в край. Теперь опорный не связан с данными - он тянется из генератора случайных чисел. Отсортированный массив больше не «ядовит»: на нём случайный опорный так же вероятно попадёт в середину, как на любом другом. Ожидаемое время становится Θ(n) на ЛЮБОМ входе - его гарантирует наша монетка, а не благосклонность данных.

Правило

У quickselect с фиксированным опорным есть худший случай Θ(n²): на «ядовитом» входе (например, отсортированном при опорном-последнем) разбиение отрезает по одному элементу, размеры идут n, n−1, …, 1, сумма квадратична. РАНДОМИЗАЦИЯ - случайный выбор опорного - делает ожидаемое время Θ(n) на ЛЮБОМ входе: плохой сценарий теперь зависит от внутренней случайности, а не от данных, и никакой противник не может его гарантировать. Худший случай остаётся ВОЗМОЖНЫМ, но становится КРАЙНЕ маловероятным и не привязанным к конкретным данным.

Разбор: «средний по входам» против «ожидаемого на любом входе»

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

Разбор: почему случайность спасает именно от подстроенного входа

Разберём, ПОЧЕМУ вредный вход перестаёт быть вредным. Фиксированный алгоритм детерминирован: по входу однозначно предсказуемо, какие опорные он возьмёт, - значит можно построить вход, на котором все они окажутся крайними. Это как известная наперёд стратегия в игре против жулика. Случайный опорный разрывает связь «вход → последовательность опорных»: даже зная весь входной массив заранее, противник не знает наших случайных чисел, поэтому не может гарантировать, что опорные будут плохими. Вероятность, что случайный опорный попадёт в «хорошую середину» (между 25-м и 75-м перцентилем участка), - целых 1/2, и такие разбиения достаточно часты, чтобы ожидаемая работа осталась линейной. Существуют детерминированные атаки на быстрые сортировки в реальных библиотеках (специально подобранные массивы, загоняющие в Θ(n²)), и защита от них - ровно рандомизация опорного. Случайность здесь - не «для красоты», а инженерная броня.

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

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

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

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

Теперь сам

Массив [1, 2, 3, 4, 5, 6, 7, 8] уже отсортирован. Опорный берём всегда последний (фиксированный). Сколько элементов отрежет первое разбиение при поиске минимума, и почему случайный опорный это чинит?