Co to jest technika dziel i zwyciężaj?
Dziel i zwyciężaj to technika konstruowania algorytmów polegająca na podzieleniu problemu na mniejsze podproblemy, rozwiązaniu ich osobno, a następnie połączeniu wyników w rozwiązanie całego zadania.
Typowy schemat wygląda następująco:
- Podziel problem na dwa lub więcej mniejszych podproblemów.
- Rozwiąż podproblemy — często rekurencyjnie.
- Połącz wyniki częściowe w końcowy wynik.
Podział trwa do momentu, gdy podproblem jest na tyle prosty, że można go rozwiązać bez dalszego dzielenia. Taki przypadek nazywa się często przypadkiem bazowym.
Przykłady algorytmów dziel i zwyciężaj
Do najpopularniejszych algorytmów wykorzystujących tę technikę należą:
- sortowanie przez scalanie — dzieli tablicę na połowy, sortuje je i scala,
- sortowanie szybkie — dzieli dane względem elementu osiowego,
- wyszukiwanie binarne — odrzuca połowę zakresu w każdym kroku,
- algorytmy geometryczne i niektóre metody mnożenia dużych liczb.
Przykład: wyszukiwanie binarne
Wyszukiwanie binarne działa na posortowanej tablicy. Zamiast sprawdzać elementy po kolei, porównuje szukaną wartość ze środkiem tablicy i wybiera tylko jedną połowę do dalszego przeszukania.
Jeśli szukana wartość jest mniejsza od środkowej,
szukaj w lewej połowie.
Jeśli jest większa,
szukaj w prawej połowie.
Ważne na egzaminie
Jeżeli w treści pytania pojawia się opis: „rozbicie problemu na mniejsze podproblemy” oraz „rozwiązywanie aż do prostych przypadków”, prawidłową odpowiedzią jest zwykle dziel i zwyciężaj. Nie należy mylić tej techniki z algorytmami heurystycznymi ani z konkretnymi problemami, takimi jak problem komiwojażera.