В этом параграфе вы познакомитесь с подходом «Разделяй и властвуй». Он помогает решать сложные задачи, разбивая их на части, обрабатывая каждую отдельно и объединяя результаты.
Важно не путать этот подход с рекурсией: рекурсия — это технический приём, когда функция вызывает саму себя, а «Разделяй и властвуй» — стратегия проектирования алгоритмов, которая почти всегда реализуется рекурсивно, но включает ещё шаг объединения решений. На примере MergeSort вы увидите, как эта стратегия используется для быстрой сортировки.
Ключевые вопросы параграфа
- В чём суть подхода «Разделяй и властвуй» и как он помогает ускорить решение задач?
- Как работает MergeSort и чем он отличается от наивных алгоритмов сортировки?
- Почему объединение результатов подзадач — не менее важный шаг, чем их решение?
Алгоритм «Разделяй и властвуй»
Одна большая задача может казаться трудной. Но если разделить её на две задачи в два раза меньше, она станет намного проще. Для таких случаев хорошо подходят алгоритмы «разделяй и властвуй».
Они так и работают: разделяют задачу на более мелкие подзадачи, независимо находят решения для них и соединяют результаты в решение изначальной задачи. Конечно, реальные ситуации бывают более сложными, чем мы описали.
После разделения одной задачи на подзадачи, алгоритм обычно делит их на ещё более мелкие под-подзадачи и так далее. Он продолжает это делать, пока не дойдёт до точки, где в рекурсии уже нет необходимости.
Важнейший шаг в работе с алгоритмами «разделяй и властвуй» — это соединить решения подзадач в решение изначальной задачи.
В качестве примера алгоритма «разделяй и властвуй» приведём задачу сортировки:
Задача сортировки и метод SelectionSort
Сортировка: Отсортируйте набор целых чисел.
- Входные данные: Список из разных чисел .
- Выходные данные: Отсортированный список целых чисел. Измененный порядок целых чисел от , где .
SelectionSort
— это простой итерационный метод решения задачи по сортировке.
- Сначала он находит самый маленький элемент в , а затем меняет его местами с первым элементом (то есть с ).
- Затем он находит второй самый маленький элемент в и переставляет его на второе место, меняя элемент местами с .
- Повторяя это действие в -й раз,
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
, состоящее из уровней, где — размер изначального неотсортированного списка.
- На нижнем уровне нам нужно объединить два отсортированных списка размером примерно в элементов, что займёт времени.
- На следующем самом высоком уровне нам нужно объединить четыре списка из элементов, что потребует времени.
Такой шаблон можно описать следующим образом: -й уровень состоит из списков, каждый из которых включает в себя приблизительно элементов и занимает времени для объединения.
Так как в рекурсивном дереве уровней, выполнение MergeSort
потребует в общем времени, что даёт нам большое ускорение по сравнению с более наивным алгоритмом сортировки.

Что дальше
Теперь вы знаете, как работает подход «Разделяй и властвуй» и как с его помощью ускорить решение задач. Вы научились использовать рекурсию, объединять подзадачи и применять это к сортировке.
Далее — рандомизированные алгоритмы. Вы увидите, как случайность может стать преимуществом в вычислениях, и узнаете, почему некоторые вероятностные алгоритмы работают быстрее, чем детерминированные.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Подход «Разделяй и властвуй» помогает решать задачи, разбивая их на части и объединяя решения.
- Алгоритм MergeSort сортирует список за O(n log n) благодаря рекурсивному делению и слиянию.
- Такие алгоритмы часто быстрее наивных и хорошо масштабируются.