6.5. Алгоритмы «Разделяй и властвуй»
Авторы: Алексей Толстиков, Александр Куликов
В этой статье вы познакомитесь с подходом «Разделяй и властвуй». Он помогает решать сложные задачи, разбивая их на части, обрабатывая каждую отдельно и объединяя результаты.
Важно не путать этот подход с рекурсией: рекурсия — это технический приём, когда функция вызывает саму себя, а «Разделяй и властвуй» — стратегия проектирования алгоритмов, которая почти всегда реализуется рекурсивно, но включает ещё шаг объединения решений. На примере MergeSort вы увидите, как эта стратегия используется для быстрой сортировки.
Ключевые вопросы статьи
- В чём суть подхода «Разделяй и властвуй» и как он помогает ускорить решение задач?
- Как работает MergeSort и чем он отличается от наивных алгоритмов сортировки?
- Почему объединение результатов подзадач — не менее важный шаг, чем их решение?
Алгоритм «Разделяй и властвуй»
Одна большая задача может казаться трудной. Но если разделить её на две задачи в два раза меньше, она станет намного проще. Для таких случаев хорошо подходят алгоритмы «разделяй и властвуй».
Они так и работают: разделяют задачу на более мелкие подзадачи, независимо находят решения для них и соединяют результаты в решение изначальной задачи. Конечно, реальные ситуации бывают более сложными, чем мы описали.
После разделения одной задачи на подзадачи, алгоритм обычно делит их на ещё более мелкие под-подзадачи и так далее. Он продолжает это делать, пока не дойдёт до точки, где в рекурсии уже нет необходимости.
Важнейший шаг в работе с алгоритмами «разделяй и властвуй» — это соединить решения подзадач в решение изначальной задачи.
В качестве примера алгоритма «разделяй и властвуй» приведём задачу сортировки:
Задача сортировки и метод SelectionSort
Сортировка: Отсортируйте набор целых чисел.
- Входные данные: Список из разных чисел .
- Выходные данные: Отсортированный список целых чисел. Измененный порядок целых чисел от , где .
SelectionSort — это простой итерационный метод решения задачи по сортировке.
- Сначала он находит самый маленький элемент в , а затем меняет его местами с первым элементом (то есть с ).
- Затем он находит второй самый маленький элемент в и переставляет его на второе место, меняя элемент местами с .
- Повторяя это действие в -й раз,
SelectionSortнаходит -й самый маленький элемент в и переставляет его на -е место.
Если ,
SelectionSort(a) будет состоять из следующих семи шагов:
Время выполнения SelectionSort квадратично, то есть : используется итераций, для каждого из которых требуется время, чтобы просканировать не более элементов и найти самый большой из них для суффикса .
Обратите внимание, что — это завышенная оценка времени выполнения, так как при -м повторе
SelectionSortсканирует суффикс размером : при первой итерации находится максимальное значение в массиве размера , при второй итерации сканируется массив размера и так далее.
Тем не менее общее время выполнения растёт как :
Алгоритм MergeSort
MergeSort — классический пример алгоритма «разделяй и властвуй» для сортировки. Он намного быстрее, чем SelectionSort.
Начнём с задачи слияния, в которой нам нужно будет объединить два отсортированных списка — и — в один отсортированный список.
Алгоритм Merge объединяет два отсортированных списка в один за время . Для этого алгоритм повторно выбирает самый маленький элемент из оставшихся в и и перемещает его в растущий отсортированный список.
Merge(List_1,List_2):
SortedList = ... // empty list
while both List_1 and List_2 are non-empty:
if the smallest element in List_1 is smaller than the smallest element in List_2:
move the smallest element from List_1 to the end of SortedList
else:
move the smallest element from List_2 to the end of SortedList
move any remaining elements from either List_1 or List_2 to the end of SortedList
return SortedList
Merge — полезный инструмент для сортировки произвольного списка, если мы знаем, как разделить неотсортированный список на две отсортированные половины.
Вам может показаться, что мы вернулись к тому, с чего начали, только теперь нам нужно отсортировать два меньших списка вместо одного большого. Но сортировка двух мелких списков — более предпочтительная алгоритмическая задача. Чтобы понять, почему это так, мы рассмотрим алгоритм MergeSort. Он разделяет неотсортированный список на две части и использует рекурсию для выполнения мелких задач перед тем, как объединить отсортированные списки.
MergeSort(List):
if List consists of a single element:
return List
FirstHalf = first half of List
SecondHalf = second half of List
SortedFirstHalf = MergeSort(FirstHalf)
SortedSecondHalf = MergeSort(SecondHalf)
SortedList = Merge(SortedFirstHalf,SortedSecondHalf)
return SortedList
Остановитесь и подумайте
Каково время выполнения MergeSort?
На рис. изображено рекурсивное дерево MergeSort, состоящее из уровней, где — размер изначального неотсортированного списка.
- На нижнем уровне нам нужно объединить два отсортированных списка размером примерно в элементов, что займёт времени.
- На следующем самом высоком уровне нам нужно объединить четыре списка из элементов, что потребует времени.
Такой шаблон можно описать следующим образом: -й уровень состоит из списков, каждый из которых включает в себя приблизительно элементов и занимает времени для объединения.
Так как в рекурсивном дереве уровней, выполнение MergeSort потребует в общем времени, что даёт нам большое ускорение по сравнению с более наивным алгоритмом сортировки.
Что дальше
Теперь вы знаете, как работает подход «Разделяй и властвуй» и как с его помощью ускорить решение задач. Вы научились использовать рекурсию, объединять подзадачи и применять это к сортировке.
Далее — рандомизированные алгоритмы. Вы увидите, как случайность может стать преимуществом в вычислениях, и узнаете, почему некоторые вероятностные алгоритмы работают быстрее, чем детерминированные.
Ключевые выводы статьи
- Подход «Разделяй и властвуй» помогает решать задачи, разбивая их на части и объединяя решения.
- Алгоритм MergeSort сортирует список за O(n log n) благодаря рекурсивному делению и слиянию.
- Такие алгоритмы часто быстрее наивных и хорошо масштабируются.