Dziel i zwyciężaj () – 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ź (). 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. ), sortowanie szybkie (ang. ), wyszukiwanie binarne (ang. ), algorytm Cooleya-Tukeya dokonujący szybkiej transformacji Fouriera, graficzny algorytm Warnocka.
Bibliografia Metoda „dziel i zwyciężaj”; materiały dydaktyczne Wydziału Matematyki i Informatyki Uniwersytetu Łódzkiego na: www.math.uni.lodz.pl/~horzel Metoda „dziel i zwyciężaj”; materiały dydaktyczne Uniwersytetu Jana Kochanowskiego w Kielcach na: www.ujk.edu.pl/~stefanek Jerzy Wałaszek, Algorytmy sortujące > Sortowanie szybkie (algorytm sortowania oparty na strategii „dziel i zwyciężaj”), materiały przeznaczone dla uczniów szkół ponadgimnazjalnych
Kategoria:Algorytmika