Одна большая задача может казаться трудной. Но если разделить её на две задачи в два раза меньше, она станет намного проще. Для таких случаев хорошо подходят алгоритмы «разделяй и властвуй». Они так и работают: разделяют задачу на более мелкие подзадачи, независимо находят решения для них и соединяют результаты в решение изначальной задачи. Конечно, реальные ситуации бывают более сложными, чем мы описали. После разделения одной задачи на подзадачи, алгоритм обычно делит их на ещё более мелкие под-подзадачи и так далее. Он продолжает это делать, пока не дойдёт до точки, где в рекурсии уже нет необходимости. Важнейший шаг в работе с алгоритмами «разделяй и властвуй» — это соединить решения подзадач в решение изначальной задачи.
В качестве примера алгоритма «разделяй и властвуй» приведём задачу сортировки:
Сортировка: Отсортируйте набор целых чисел.
- Входные данные: Список из $n$ разных чисел $a = (a_1, a_2, \dotsc , a_n)$.
- Выходные данные: Отсортированный список целых чисел. Измененный порядок $(b_1, b_2, \dotsc , b_n)$ целых чисел от $a$, где $b_1 < b_2 < \dotsb < b_n$.
SelectionSort
— это простой итерационный метод решения задачи по сортировке. Сначала он находит самый маленький элемент в $a$, а затем меняет его местами с первым элементом (то есть с $a_1$). Затем он находит второй самый маленький элемент в $a$ и переставляет его на второе место, меняя элемент местами с $a_2$. Повторяя это действие в $i$-й раз, SelectionSort
находит $i$-й самый маленький элемент в $a$ и переставляет его на $i$-е место.
Если $a = (7, 92, 87, 1, 4, 3, 2, 6)$, SelectionSort(a)
будет состоять из следующих семи шагов:
Время выполнения SelectionSort
квадратично, то есть $O(n^2)$: используется $n$ итераций, для каждого из которых требуется время, чтобы просканировать не более $n$ элементов и найти самый большой из них для суффикса $a$. Обратите внимание, что $n^2$ — это завышенная оценка времени выполнения, так как при $i$-м повторе SelectionSort
сканирует суффикс размером $n-i+1$: при первой итерации находится максимальное значение в массиве размера $n$, при второй итерации сканируется массив размера $n-1$ и так далее. Тем не менее общее время выполнения растёт как $n^2$:
$$ n+(n-1)+(n-2)+\dotsb+2+1=\frac{n(n+1)}{2} , $$
MergeSort
— классический пример алгоритма «разделяй и властвуй» для сортировки. Он намного быстрее, чем SelectionSort
. Начнём с задачи слияния, в которой нам нужно будет объединить два отсортированных списка — $List_1$ и $List_2$ — в один отсортированный список.
Алгоритм Merge
объединяет два отсортированных списка в один за время $O(|List_1| + |List_2|)$. Для этого алгоритм повторно выбирает самый маленький элемент из оставшихся в $List_1$ и $List_2$ и перемещает его в растущий отсортированный список.
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
, состоящее из $\log_2 n$ уровней, где $n$ — размер изначального неотсортированного списка. На нижнем уровне нам нужно объединить два отсортированных списка размером примерно в $n /2$ элементов, что займёт $O(n /2 + n /2) = O(n)$ времени. На следующем самом высоком уровне нам нужно объединить четыре списка из $n /4$ элементов, что потребует $O(n /4 + n /4 + n /4 + n /4) = O(n)$ времени. Такой шаблон можно описать следующим образом: $i$-й уровень состоит из $2^i$ списков, каждый из которых включает в себя приблизительно $n /2^i $ элементов и занимает $O(n)$ времени для объединения. Так как в рекурсивном дереве $\log_2 n$ уровней, выполнение MergeSort
потребует в общем $O(n \log_2 n)$ времени, что даёт нам большое ускорение по сравнению с более наивным $O(n^2)$ алгоритмом сортировки.