Dziel i zwyciężaj

Jest to jedna z głównych metod projektowania algorytmów w informatyce, prowadząca do bardzo efektywnych rozwiązań. W strategii tej postępowanie opiera się na następującej zasadzie: jeśli problem jest tak mały, że umiesz go rozwiązać to go rozwiąż, a jeśli nie to podziel go na mniejsze podproblemy i spróbuj ponownie. Innymi słowy problem dzieli się rekurencyjnie na dwa lub więcej mniejszych podproblemów tego samego (lub podobnego) typu tak długo, aż fragmenty staną się wystarczająco proste do bezpośredniego rozwiązania. Z kolei rozwiązania otrzymane dla podproblemów scala się, uzyskując rozwiązanie całego zadania.

Podstawowe algorytmy bazujące na tej metodzie, to:

• sortowanie przez scalanie (mergesort),

• sortowanie szybkie (quicksort),

• wyszukiwanie binarne (binary search),

• znajdowanie zera funkcji metodą bisekcji,