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

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

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

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

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

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

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

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

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, состоящее из уровней, где — размер изначального неотсортированного списка. На нижнем уровне нам нужно объединить два отсортированных списка размером примерно в элементов, что займёт времени. На следующем самом высоком уровне нам нужно объединить четыре списка из элементов, что потребует времени. Такой шаблон можно описать следующим образом: -й уровень состоит из списков, каждый из которых включает в себя приблизительно $n /2^i $ элементов и занимает времени для объединения. Так как в рекурсивном дереве уровней, выполнение MergeSort потребует в общем времени, что даёт нам большое ускорение по сравнению с более наивным алгоритмом сортировки.