dziel i zwyciężaj

Dziel i zwyciężaj (ang. divide and conquer) – jedna z głównych metod projektowania algorytmów w informatyce, prowadząca do bardzo efektywnych rozwiązań. Nazwa pochodzi od łacińskiej sentencji dziel i rządź (łac. divide et impera). W strategii tej 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. Algorytmami korzystającymi z tej metody są m.in.: * sortowanie przez scalanie (ang. mergesort), * sortowanie szybkie (ang. quicksort), * wyszukiwanie binarne (ang. binary search), * algorytm Cooleya-Tukeya dokonujący szybkiej transformacji Fouriera, * graficzny algorytm Warnocka.