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.
Klasyczne przykłady algorytmów korzystających z tej metody to m.in. sortowanie przez scalanie (mergesort), sortowanie szybkie (quicksort), wyszukiwanie binarne (binary search).
rozdz. w podr. 1.7.
Brak komentarzy:
Prześlij komentarz