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

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

Алгоритм «разделяй и властвуй» помогает решать большие задачи. Вот как это происходит:

1. Разбиваем задачу на более мелкие подзадачи.
2. Решаем подзадачи. 
3. Объединяем их и получаем желаемый результат.

Чтобы использовать алгоритм «разделяй и властвуй», понадобятся знания о рекурсии. 

Как работает алгоритм

Алгоритм стоит из 3 шагов: 

• Разделяй. Разделяем задачу на подзадачи с помощью рекурсии.
• Властвуй. Как только задачи станут достаточно малы — рекурсивно решаем. 
• Объединяй. Объединяем все подзадачи в одно целое, чтобы получить решение исходной задачи.

Разберем этот алгоритм на примере.

Мы будем выполнять сортировку слиянием с помощью алгоритма «разделяй и властвуй».

1. Пусть дан следующий массив: 

2. Делим его пополам:

Рекурсивно делим подмассивы до тех пор, пока не останутся только отдельные элементы.

3. Объединяем и сортируем отдельные элементы. На этом этапе мы властвуем и объединяем:

Временная сложность

Сложность алгоритма «разделяй и властвуй» вычисляется с помощью основной теоремы о рекуррентных соотношениях:

T(n) = aT(n/b) + f(n)

Здесь:

• n — объем входных данных.
• a — количество подзадач в рекурсии.
• n/b — размер каждой подзадачи. Предполагается, что все подзадачи имеют одинаковый размер.
• f(n) — оценка выполненной работы вне рекурсивных вызовов. Также она включает в себя вычислительную стоимость деления на подзадачи и объединения решений этих подзадач.

Попробуем найти временную сложность рекурсивной задачи.

В качестве примера возьмем сортировку слиянием. Уравнение принимает следующий вид: 

T(n) = aT(n/b) + f(n)
     = 2T(n/2) + O(n)

Здесь:

• a = 2 (на каждом шаге задача делится на две подзадачи);
• n/b = n/2 (размер каждой подзадачи — половина исходной);
• f(n) = затраченное время на деление задачи на подзадачи и их последующее объединение;
• T(n/2) = O(n log n) (чтобы понять это выражение, прочтите эту статью).

В конечном итоге 

T(n) = 2T(n log n) + O(n)
          ≈ O(n log n)

«Разделяй и властвуй» vs. динамическое программирование 

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

Используйте метод «разделяй и властвуй», когда все подзадачи дают разный результат. Динамическое программирование лучше использовать, когда результаты вычислений подзадач могут совпадать. 

Разберем пример. Допустим, мы пытаемся найти числа Фибоначчи. 

«Разделяй и властвуй»

fib(n)
    If n < 2, return 1
    Else , return f(n - 1) + f(n -2)

Динамическое программирование

mem = []
fib(n)
    If n in mem: return mem[n] 
    else,     
        If n < 2, f = 1
        else , f = f(n - 1) + f(n -2)
        mem[n] = f
        return f

В этой программе все результаты вычислений подзадач содержатся в mem.

Преимущества алгоритма

• Сложность умножения двух матриц с помощью примитивного метода — O(n³). А вот сложность метода «разделяй и властвуй» (умножение матриц методом Штрассена) — O(n^2.8074).
• Идеально подходит для многоядерных систем.
• Эффективно использует кэш-память.

Где применяется

• Бинарный поиск.
• Сортировка слиянием.
• Быстрая сортировка. 
• Умножение матриц методом Штрассена.
• Алгоритм Карацубы.