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