Informatyka MIMUW

Metoda ta polega na podzieleniu problemu na podproblemy, które rozwiązujemy niezależnie, a następnie "scalamy". Metoda działa dobrze, gdy "scalanie" podproblemów jest łatwe, oraz same podproblemy są "małe" w stosunku do rozmiaru problemu $n$.

Jako przykład rozważmy jeszcze raz problem wyznaczenia przywódcy tablicy (patrz Wstęp: poprawność i złożoność algorytmów.). Stosując metodę dziel i zwyciężaj, możemy otrzymać następujący algorytm:

Algorytm Rekurencyjny Przywódca

if  n=1  then przywódcą jest pojedynczy element tablicy 
else 
     podziel tablicę na dwie połowy; 
     rekurencyjnie oblicz przywódcę lewej i prawej połowy tablicy; 
    sprawdź w czasie  O(n), który z nich jest przywódcą całości

Jeśli algorytm ten wykonuje $T(n)$ kroków, to:

$T(n)\ =\ T(\lfloor \frac{n}{2}\rfloor)+T(\lceil \frac{n}{2}\rceil)+O(n),\ T(1)=1$

Rozwiązaniem jest $T(n)=O(n \log n)$ (jak wiadomo z kursu matematyki dyskretnej).