Разделяй и владей Алгоритъм

В този урок ще научите как работи алгоритъмът „разделяй и владей“. Също така ще сравним подхода „разделяй и владей“ с други подходи за решаване на рекурсивен проблем.

А разделяй и владей алгоритъм е стратегия за решаване на голям проблем, като

разбиване на проблема на по-малки подпроблеми
решаване на подпроблемите и
комбинирането им, за да се получи желаната продукция.

За да се използва алгоритъма за разделяне и завладяване, се използва рекурсия . Научете за рекурсията на различни езици за програмиране:

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

Как работят алгоритмите за разделяне и завладяване?

Ето стъпките:

Разделяне : Разделете зададения проблем на подзадачи с помощта на рекурсия.
Conquer : Решаване на по-малките подзадачи рекурсивно. Ако подпроблемата е достатъчно малка, разрешете я директно.
Комбиниране: Комбинирайте решенията на подзадачите, които са част от рекурсивния процес, за да решите действителния проблем.

Нека разберем тази концепция с помощта на пример.

Тук ще сортираме масив, използвайки подхода разделяне и завладяване (т.е. сливане на сортиране).

Нека даденият масив да бъде: Масив за сортиране на сливане
Разделете масива на две половини. Разделете масива на две подчасти
Отново разделете всяка подчаст рекурсивно на две половини, докато получите отделни елементи. Разделете масива на по-малки части
Сега комбинирайте отделните елементи по сортиран начин. Тук завладявайте и комбинирайте стъпки вървете рамо до рамо. Комбинирайте частите

Сложност във времето

Сложността на алгоритъма разделяне и завладяване се изчислява с помощта на главната теорема.

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: върнете mem (n) else, Ако n <2, f = 1 друго, f = f (n - 1) + f (n -2) mem (n) = f връщане f

При динамичен подход mem съхранява резултата от всяка подпроблема.

Предимства на алгоритъма за разделяне и завладяване

Сложността на умножението на две матрици, използвайки наивния метод, е O (n ³ ), докато използването на подхода разделяне и завладяване (т.е. умножението на матрицата на Strassen) е O (n ^2.8074 ). Този подход опростява и други проблеми, като Ханойската кула.
Този подход е подходящ за многопроцесорни системи.
Той ефективно използва кешовете на паметта.