Два разных «в среднем»: по входам и по монетке

Если понимаешь, почему рандомизированный quicksort быстр на любом входе, а обычный - нет, - листай до «Теперь сам».

Как думаешь, где подвох

Быстрая сортировка (quicksort) устроена так: выбирают один элемент - опорный, раскладывают остальные на «меньше опорного» и «больше», а потом так же сортируют каждую из двух частей. Если опорный делит список примерно пополам, получается log n уровней по n работы - Θ(n·log n) (это как деление пополам из главы про суммы). Разбор точного среднего - в разделе про сортировки; здесь нам хватит этой картинки.

Обычный quicksort берёт опорным первый элемент. На случайном входе он в среднем Θ(n·log n). Но подай ему уже отсортированный список - и он выродится в Θ(n²): первый элемент отсортированного списка - наименьший, значит в часть «меньше» не попадает никто, а в «больше» - все n-1; деления пополам нет, уровней n, на каждом работа до n. А ведь отсортированный вход - не экзотика, он встречается сплошь и рядом. Как же тогда им пользуются? Ответ: опорный выбирают СЛУЧАЙНО - и n² исчезает для всех входов сразу. Почему одна случайная строчка меняет гарантию - об этом урок.

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

Первое «в среднем» - ставка на обычную погоду: в среднем по году тепло, но конкретный день может оказаться бураном, и если ты каждый день выходишь в одном и том же месте, буран тебя найдёт. Второе - ты сам тасуешь колоду перед раздачей: какую бы колоду тебе ни подсунули, твоя карта случайна, и подстроить её нельзя. Случайность либо снаружи (во входах, и тогда её кто-то контролирует), либо внутри алгоритма (в его монетке, и тогда её не контролирует никто).

Механизм: над чем берут ожидание

Средний случай (по входам). Алгоритм фиксирован, детерминирован. Берём ожидание времени по входам, взятым из некоторого РАСПРЕДЕЛЕНИЯ - обычно предполагают, что все входы размера n равновероятны. Вывод зависит от этого предположения: если в жизни входы не такие (часто уже почти отсортированы, например), «средний» не выполняется. Хуже того: противник, знающий твой алгоритм, подберёт худший вход и будет подавать его каждый раз - никакой случайности во входе нет, она вся в твоём (неверном) предположении.

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

Правило

«Средний случай» - ожидание по распределению входов: держится при предположении о входах, имеет плохие входы. «Рандомизированное среднее» - ожидание по случайным выборам алгоритма: держится на любом входе, плохих входов нет, есть лишь маловероятное невезение. Первое защищает предположение, второе - монетка.

Разбор: отсортированный вход и две сортировки

Дай обеим сортировкам уже отсортированный список. Детерминированный quicksort с опорным-первым проваливается в Θ(n²): на нём его «средний по входам» не работает, потому что этот вход - как раз худший, а он вовсе не «в среднем». Рандомизированный quicksort на том же входе - Θ(n·log n) ожидаемо: он выбирает опорный случайно, и отсортированность входа ему безразлична. Один и тот же вход: у первого он вскрывает худший случай, у второго - рядовой.

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

Рандомизированный алгоритм не отменяет Θ(n²) - он делает его недостижимым по заказу. Чтобы получить n², монетка должна раз за разом выбирать почти крайний опорный, а вероятность такого исчезающе мала и не зависит от того, какой список подали. Разница с детерминированным - не в том, что худшего нет, а в том, что к нему нельзя ПРИНУДИТЬ входом: нет строки данных, которая гарантированно роняет алгоритм. Для защиты от злонамеренных входов это и есть всё.

Насколько мала вероятность? Чтобы рандомизированный quicksort выродился в n², монетка должна раз за разом выбирать почти крайний опорный - вероятность такого исчезающе мала и быстро падает с ростом n: на списке в тысячу элементов словить квадрат практически невозможно. И, главное, эта вероятность ОДИНАКОВА для любого входа: ни отсортированный список, ни собранный врагом не повышают её ни на столько. Врагу нечего подать - монетка не в его руках.

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

Главная ошибка - положиться на «средний случай O(n·log n)», когда входы не случайны. В проде данные часто уже отсортированы, сгруппированы или присланы тем, кто хочет тебя уронить, - и детерминированный алгоритм со «средним по входам» получает свой худший случай стабильно, а не изредка. Это называется атакой на сложность: злоумышленник шлёт ровно те данные, что вырождают твой алгоритм. Лечит её именно перенос случайности ВНУТРЬ алгоритма.

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

Поэтому стандартные библиотеки сортируют рандомизированным quicksort (или его защищённым вариантом). То же и с хеш-таблицами - структурами, которые ищут за O(1), раскладывая ключи по ячейкам по значению хеш-функции (подробно в разделе про хеширование): к хеш-функции подмешивают случайное зерно, потому что без него противник подберёт ключи, которые все лягут в одну ячейку, и O(1) выродится в O(n) - тот же приём «случайность внутрь алгоритма». Выбор «средний случай или рандомизация» - это выбор, кто контролирует случайность: если входы могут быть враждебными, её уводят внутрь алгоритма, где до неё не дотянуться.

Теперь сам

Какое из двух «в среднем» требует предположения о том, как распределены входы, а какое защищает от злонамеренно подобранного входа?