Если у вас есть монетка, то прежде чем начать искать телефон, вы можете подбросить её и решить, откуда начать поиск: если выпадет решка, то сначала ищем на первом этаже, если орёл — на втором. А для выбора конкретной комнаты можно использовать игральный кубик. Хотя бросать монеты и кубики весело, этот подход однозначно не интуитивен. К тому же непонятно, даёт ли это алгоритмическое преимущество по сравнению с детерминированным алгоритмом. Наши задачи помогут разобраться, в каких ситуациях вероятностные алгоритмы будут лучше детерминированных.
Чтобы продемонстрировать пример вероятностного алгоритма, обсудим сначала быстрый метод сортировки, который называется QuickSort. Для упрощения будем считать, что все элементы данного массива разные.
QuickSort выбирает элемент (например, первый) из и просто разделяет массив на два подмассива: , в который входят все элементы меньше ; и , в который входят все элементы больше .
Это разделение можно выполнить за линейное время, далее, следуя стратегии «разделяй и властвуй», QuickSort рекурсивно сортирует каждый подмассив. Итоговый отсортированный список может быть легко получен с помощью конкатенации отсортированного , элемента и отсортированного .
QuickSort(c):
if |c| = 1: // только один элемент
return c
m = c[1] // возьмем первый элемент c
// определим элементы c_small меньше m
// определим элементы c_large больше m
QuickSort(c_small)
QuickSort(c_large)
// объединим c_small, m и c_large в сортированный список c_sorted
return c_sorted
Для данного подхода требуется выделить дополнительную память, в которой будут храниться массивы и . Лучший подход — переставить элементы входного массива на месте, чтобы набор шёл первым, затем , а затем (см. ниже) — однако неясно, как это сделать.
✒️ Упражнение:
Нико Ломуто предложил изящный алгоритм, позволяющий выполнить такую перестановку элементов на месте. Рисунок ниже показывает, как работает разбиение Ломуто. Посмотрите на рисунок. Сможете ли вы воссоздать логику подхода Ломуто?
Оказывается, что время выполнения QuickSort зависит от нашей удачи при отборе элемента . Если мы выберем так, что массив разделяется на две равные части (то есть ), тогда
где означает время, которое требуется QuickSort для сортировки массива из чисел, и означает время, которое потребуется для разделения массива длины на две части; — положительная константа. Это абсолютно такое же рекуррентное соотношение, как и в MergeSort, соответствующее времени выполнения .
Тем не менее если мы выберем так, что разделится неровно (например, возникает крайний случай, когда набор пуст, а в наборе элементов), тогда рекуррентное соотношение будет
Это соотношение и приводит к времени выполнения , а этого мы пытаемся избежать. Сортировка массива с помощью QuickSort действительно занимает квадратичное время. Что ещё хуже, на обработку требуется время . Это выглядит излишним, ведь массив уже отсортирован.
Пока что алгоритм QuickSort похож на плохую имитацию MergeSort. Однако если мы сможем выбрать хороший «разделитель» , который разбивает массив на две равные части, мы сможем улучшить время выполнения. На самом деле, не обязательно пытаться достичь идеального разделения (50/50), чтобы получить время выполнения . Например, также подойдет разделение на примерно равные части (скажем, 51/49). Фактически можно доказать, что алгоритм будет иметь время выполнения при условии, что оба набора и больше, чем .
Из этого следует, что из возможных вариантов для , выбранного в качестве элементов массива , как минимум хорошо подойдут для разделения! Другими словами, если мы возьмем случайным образом (вероятность выбрать любой из элементов одинакова), то у нас будет шанс 50% получить хорошее разделение. Такой вывод ложится в основу следующего вероятностного алгоритма:
RandomizedQuickSort(c):
if |c| = 1: // только один элемент
return c
m = ... // возьмем случайный элемент из c
// определим элементы c_small меньше m
// определим элементы c_large больше m
RandomizedQuickSort(c_small)
RandomizedQuickSort(c_large)
// объединим c_small, m и c_large в сортированный список c_sorted
return c_sorted
На практике RandomizedQuickSort — это быстрый алгоритм. Однако его худшее время выполнения остается , так как все еще есть вероятность, что он выберет плохой разделитель. При одном и том же вводе поведение вероятностного алгоритма отличается от одного выполнения к другому. Тем не менее мы можем доказать, что его ожидаемое время выполнения — . Слово «ожидаемое» подмечает следующий эффект. Так как RandomizedQuickSort — это вероятностный алгоритм, два разных запуска (при одинаковом вводе) могут занять разное количество времени: некоторые будут быстрыми, некоторые — медленными. Таким образом, время выполнения вероятностного алгоритма — это случайная величина. Разработчики нередко интересуются средним значением этой случайной величины, что и называется ожидаемым временем выполнения. Можно продемонстрировать, что для каждого массива размером в ожидаемое время выполнения RandomizedQuickSort будет .
Главное преимущество вероятностных алгоритмов — это производительность. Вероятностные алгоритмы решают многие реальные задачи быстрее (с точки зрения ожидаемого времени выполнения), чем детерминированные алгоритмы. Еще одна привлекательная особенность — это их простота. Она демонстрируется, например, в RandomizedQuickSort.
Мы подчеркиваем, что хотя RandomizedQuickSort и принимает решения случайным образом, он всегда выдаёт правильное решение задачи сортировки. Единственный изменяющийся параметр от одного прогона к другому — это время выполнения, но не результат. В противоположность этому, другие вероятностные алгоритмы обычно приводят к неправильным (или точнее, приблизительным) решениям. Вероятностные алгоритмы, которые всегда дают верные решения, называются Лас-Вегас. Алгоритмы, которые не приводят к верным решениям — Монте-Карло.