Metoda dziel i zwyciężaj

WPROWADZENIE

https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm

[Cormen] Wiele algorytmów ma strukturę rekurencyjną. W celu rozwiązania danego problemu algorytmy wywołują same siebie przy rozwiązywaniu podobnych podproblemów. W podejściu dziel i zwyciężaj (divide-and-conquer) każdy poziom rekurencji składa się z następujących trzech etapów:

• Dziel (Divide): Dzielimy problem na pewną liczbę podproblemów, stanowiących mniejsze egzemplarze tego samego lub zbliżonego problemu.
• Zwyciężaj (Conquer): Rozwiązujemy podproblemy rekurencyjnie. Jeśli jednak rozmiary podproblemów są dostatecznie małe, to rozwiązujemy podproblemy bezpośrednio.
• Połącz (Combine): Łączymy rozwiązania podproblemów w rozwiązanie pierwotnego problemu.

Przykłady zastosowania:

• Jednoczesne znajdowanie minimum i maksimum ciągu.
• Wyszukiwanie binarne.
• Sortowanie ciągu metodą quicksort (sortowanie szybkie).
• Sortowanie przez scalanie (mergesort).
• Algorytm quickhull znajdowania otoczki wypukłej.
• Problem wież Hanoi.
• Algorytm Strassena mnożenia macierzy N x N (Wróblewski s. 214).
• Algorytm Karacuby (1960) szybkiego mnożenia dużych liczb całkowitych
  https://en.wikipedia.org/wiki/Karatsuba_algorithm