6.5. Алгоритмы «Разделяй и властвуй»

В этом параграфе вы познакомитесь с подходом «Разделяй и властвуй». Он помогает решать сложные задачи, разбивая их на части, обрабатывая каждую отдельно и объединяя результаты.

Важно не путать этот подход с рекурсией: рекурсия — это технический приём, когда функция вызывает саму себя, а «Разделяй и властвуй» — стратегия проектирования алгоритмов, которая почти всегда реализуется рекурсивно, но включает ещё шаг объединения решений. На примере MergeSort вы увидите, как эта стратегия используется для быстрой сортировки.

Ключевые вопросы параграфа

• В чём суть подхода «Разделяй и властвуй» и как он помогает ускорить решение задач?
• Как работает MergeSort и чем он отличается от наивных алгоритмов сортировки?
• Почему объединение результатов подзадач — не менее важный шаг, чем их решение?

Алгоритм «Разделяй и властвуй»

Одна большая задача может казаться трудной. Но если разделить её на две задачи в два раза меньше, она станет намного проще. Для таких случаев хорошо подходят алгоритмы «разделяй и властвуй».

Они так и работают: разделяют задачу на более мелкие подзадачи, независимо находят решения для них и соединяют результаты в решение изначальной задачи. Конечно, реальные ситуации бывают более сложными, чем мы описали.

После разделения одной задачи на подзадачи, алгоритм обычно делит их на ещё более мелкие под-подзадачи и так далее. Он продолжает это делать, пока не дойдёт до точки, где в рекурсии уже нет необходимости.

Важнейший шаг в работе с алгоритмами «разделяй и властвуй» — это соединить решения подзадач в решение изначальной задачи.

В качестве примера алгоритма «разделяй и властвуй» приведём задачу сортировки:

Задача сортировки и метод SelectionSort

Сортировка: Отсортируйте набор целых чисел.

• Входные данные: Список из разных чисел .
• Выходные данные: Отсортированный список целых чисел. Измененный порядок целых чисел от , где .

SelectionSort — это простой итерационный метод решения задачи по сортировке.

1. Сначала он находит самый маленький элемент в , а затем меняет его местами с первым элементом (то есть с ).
2. Затем он находит второй самый маленький элемент в и переставляет его на второе место, меняя элемент местами с .
3. Повторяя это действие в -й раз, SelectionSort находит -й самый маленький элемент в и переставляет его на -е место.

Если ,
SelectionSort(a) будет состоять из следующих семи шагов:

Время выполнения SelectionSort квадратично, то есть : используется итераций, для каждого из которых требуется время, чтобы просканировать не более элементов и найти самый большой из них для суффикса .

Обратите внимание, что — это завышенная оценка времени выполнения, так как при -м повторе SelectionSort сканирует суффикс размером : при первой итерации находится максимальное значение в массиве размера , при второй итерации сканируется массив размера и так далее.

Тем не менее общее время выполнения растёт как :

Алгоритм MergeSort

MergeSort — классический пример алгоритма «разделяй и властвуй» для сортировки. Он намного быстрее, чем SelectionSort.

Начнём с задачи слияния, в которой нам нужно будет объединить два отсортированных списка — и — в один отсортированный список.

Алгоритм Merge объединяет два отсортированных списка в один за время . Для этого алгоритм повторно выбирает самый маленький элемент из оставшихся в и и перемещает его в растущий отсортированный список.

1Merge(List_1,List_2):
2    SortedList = ... // empty list
3    while both List_1 and List_2 are non-empty:
4    if the smallest element in List_1 is smaller than the smallest element in List_2:
5        move the smallest element from List_1 to the end of SortedList
6    else:
7        move the smallest element from List_2 to the end of SortedList
8    move any remaining elements from either List_1 or List_2 to the end of SortedList
9    return SortedList

Merge — полезный инструмент для сортировки произвольного списка, если мы знаем, как разделить неотсортированный список на две отсортированные половины.

Вам может показаться, что мы вернулись к тому, с чего начали, только теперь нам нужно отсортировать два меньших списка вместо одного большого. Но сортировка двух мелких списков — более предпочтительная алгоритмическая задача. Чтобы понять, почему это так, мы рассмотрим алгоритм MergeSort. Он разделяет неотсортированный список на две части и использует рекурсию для выполнения мелких задач перед тем, как объединить отсортированные списки.

1MergeSort(List):
2     if List consists of a single element:
3        return List
4     FirstHalf = first half of List
5     SecondHalf = second half of List
6     SortedFirstHalf = MergeSort(FirstHalf)
7     SortedSecondHalf = MergeSort(SecondHalf)
8     SortedList = Merge(SortedFirstHalf,SortedSecondHalf)
9     return SortedList

Остановитесь и подумайте:
Каково время выполнения MergeSort?

На рис. изображено рекурсивное дерево MergeSort, состоящее из уровней, где — размер изначального неотсортированного списка.

1. На нижнем уровне нам нужно объединить два отсортированных списка размером примерно в элементов, что займёт времени.
2. На следующем самом высоком уровне нам нужно объединить четыре списка из элементов, что потребует времени.

Такой шаблон можно описать следующим образом: -й уровень состоит из списков, каждый из которых включает в себя приблизительно элементов и занимает времени для объединения.

Так как в рекурсивном дереве уровней, выполнение MergeSort потребует в общем времени, что даёт нам большое ускорение по сравнению с более наивным алгоритмом сортировки.

Что дальше

Теперь вы знаете, как работает подход «Разделяй и властвуй» и как с его помощью ускорить решение задач. Вы научились использовать рекурсию, объединять подзадачи и применять это к сортировке.

Далее — рандомизированные алгоритмы. Вы увидите, как случайность может стать преимуществом в вычислениях, и узнаете, почему некоторые вероятностные алгоритмы работают быстрее, чем детерминированные.

А пока вы не ушли дальше — закрепите материал на практике:

• Отметьте, что урок прочитан, при помощи кнопки ниже.
• Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
• Перейдите к задачам этого параграфа и потренируйтесь.
• Перед этим — загляните в короткий гайд о том, как работает система проверки.

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

• Подход «Разделяй и властвуй» помогает решать задачи, разбивая их на части и объединяя решения.
• Алгоритм MergeSort сортирует список за O(n log n) благодаря рекурсивному делению и слиянию.
• Такие алгоритмы часто быстрее наивных и хорошо масштабируются.