Metoda dziel i zwyciężaj

Metoda "dziel i zwyciężaj" może jedynie zostać zastosowana do problemów o strukturze rekurencyjnej, czyli takich, których podproblemy "wyglądają" tak samo i dadzą się rozwiązać tą samą metodą.
Jak sama nazwa wskazuje metoda polega na podzieleniu problemu na kilka mniejszych podproblemów (najczęściej na dwa, pół na pół), osobnym rozwiązaniu tych podproblemów i połączeniu wyników w jedno rozwiązanie całego problemu. Oczywiście podproblemy rozwiązujemy w taki sam sposób (wszystko rekurencyjnie), chyba że są na tyle małe (niepodzielne na mniejsze), że trzeba je "ręcznie" rozwiązać.
Właściwie to metoda powinna nazywać się "dziel, zwyciężaj i połącz", ale wtedy jej nazwa zostałaby pozbawiona charakterystycznego patosu :).

To jeszcze raz, nieco ogólniej:

1. Dziel - dzielimy problem na kilka podproblemów.
2. Zwyciężaj - rozwiązujemy podproblemy rekurencyjnie, chyba że ich rozmiar jest na tyle mały, że nie można zastosować rekurencji (wtedy rozwiązujemy je metodą "na chłopski rozum").
3. Połącz - łączymy rozwiązania podproblemów, aby otrzymać rozwiązanie całego problemu.

Dowód poprawności algorytmów skonstruowanych w ten sposób nie jest trudny. Wszystko sprowadza się do zastosowania indukcji matematycznej. Wystarczy jedynie udowodnić, że mając poprawnie rozwiązane podproblemy możemy je połączyć w poprawnie rozwiązany problem, co zazwyczaj wynika bezpośrednio z użytego algorytmu.

Podstawową zaletą tej metody jest złożoność czasowa. Algorytmy "dziel i zwyciężaj" zazwyczaj są szybsze od innych algorytmów rozwiązujących ten sam problem.

Sprawdźmy metodę "dziel i zwyciężaj" na przykladzie algorytmu sortowania.

Algorytm działa rekursywnie - wybierany jest pewien element tablicy, tzw. element osiowy, wszystkie elementy mniejszego od niego muszą znaleźć się po jego lewej stronie, zaś większe po prawej. Potem sortuje się osobno lewą i prawą część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa podtablica nie wymaga sortowania.

Jeśli przez l oznacza się indeks pierwszego, a przez r – ostatniego elementu sortowanego fragmentu tablicy, zaś przez i – indeks elementu, na którym tablica została podzielona, to procedurę sortowania można (w dużym uproszczeniu) przedstawić następującym, pascalo-podobnym zapisem:

  PROCEDURE Quicksort(l, r)
  BEGIN
    IF l < r THEN                { jeśli fragment dłuższy niż 1 element }
    BEGIN
      i = PodzielTablice(l, r);  { podziel i zapamiętaj punkt podziału }
      Quicksort(l, i-1);         { posortuj lewą część }
      Quicksort(i, r);           { posortuj prawą część }
    END
  END

Algorytm sortowania szybkiego jest bardzo wydajny: jego średnia złożoność obliczeniowa jest rzędu O(n * log n). Jego szybkość i prostota implementacji powodują, że jest powszechnie używany; jego implementacje znajdują się również w standardowych bibliotekach języków programowania - na przykład w bibliotece standardowej języka C (funkcja qsort), w implementacji klasy TList w Delphi, jako procedura standardowa w PHP itp.