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

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

Алгоритм разделяй и властвуй стратегия решения большой проблемы путем

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

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

Рекурсия в Java
Рекурсия в Python
Рекурсия в C ++

Как работают алгоритмы «разделяй и властвуй»?

Вот шаги:

Разделить : разделите данную проблему на подзадачи с помощью рекурсии.
Победить : рекурсивно решать более мелкие подзадачи. Если подзадача достаточно мала, решите ее напрямую.
Объединить: объединить решения подзадач, которые являются частью рекурсивного процесса, для решения актуальной проблемы.

Давайте разберемся с этой концепцией на примере.

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

Пусть данный массив будет: Массив для сортировки слиянием
Разделите массив на две половины. Разделите массив на две части.
Снова разделите каждую часть рекурсивно на две половины, пока не получите отдельные элементы. Разделите массив на более мелкие части
Теперь объедините отдельные элементы в отсортированном виде. Здесь побеждайте и соединяйте шаги бок о бок. Объедините подчасти

Сложность времени

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

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 (каждый раз проблема делится на 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)

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

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

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

Давайте разберемся в этом на примере. Предположим, мы пытаемся найти ряд Фибоначчи. Потом,

Подход «разделяй и властвуй»:

 fib (n) Если n <2, вернуть 1 Else, вернуть f (n - 1) + f (n -2)

Динамический подход:

 mem = () fib (n) Если n в памяти: вернуть mem (n) else, Если n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f возврат f

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

Преимущества алгоритма разделяй и властвуй

Сложность умножения двух матриц с использованием наивного метода составляет O (n ³ ), тогда как при использовании подхода «разделяй и властвуй» (т. ^Е. Умножения матриц Штрассена) составляет O (n ^2,8074 ). Этот подход также упрощает другие проблемы, такие как Ханойская башня.
Этот подход подходит для многопроцессорных систем.
Он эффективно использует кеши памяти.