DAA - Divide & Conquer

Wiele algorytmów ma charakter rekurencyjny i rozwiązuje dany problem rekurencyjnie, zajmując się podproblemami.

W divide and conquer approach, problem jest dzielony na mniejsze problemy, następnie mniejsze problemy są rozwiązywane niezależnie, a na koniec rozwiązania mniejszych problemów łączy się w rozwiązanie dużego problemu.

Generalnie algorytmy dziel i rządź składają się z trzech części -

Divide the problem na szereg podproblemów, które są mniejszymi przypadkami tego samego problemu.
Conquer the sub-problemsrozwiązując je rekurencyjnie. Jeśli są wystarczająco małe, rozwiąż podproblemy jako przypadki podstawowe.
Combine the solutions do podproblemów do rozwiązania pierwotnego problemu.

Plusy i minusy podejścia Divide and Conquer

Podejście dziel i zwyciężaj wspiera paralelizm, ponieważ podproblemy są niezależne. W związku z tym algorytm zaprojektowany przy użyciu tej techniki może działać w systemie wieloprocesorowym lub na różnych maszynach jednocześnie.

W tym podejściu większość algorytmów jest projektowanych przy użyciu rekurencji, stąd zarządzanie pamięcią jest bardzo wysokie. W przypadku rekurencyjnych funkcji używany jest stos, w którym stan funkcji musi być przechowywany.