DAA - Teilen & Erobern

Viele Algorithmen sind rekursiver Natur, um ein bestimmtes Problem zu lösen, das sich rekursiv mit Unterproblemen befasst.

Im divide and conquer approachwird ein Problem in kleinere Probleme unterteilt, dann werden die kleineren Probleme unabhängig voneinander gelöst, und schließlich werden die Lösungen kleinerer Probleme zu einer Lösung für das große Problem kombiniert.

Im Allgemeinen bestehen Divide-and-Conquer-Algorithmen aus drei Teilen:

Divide the problem in eine Reihe von Unterproblemen, die kleinere Instanzen desselben Problems sind.
Conquer the sub-problemsdurch rekursives Lösen. Wenn sie klein genug sind, lösen Sie die Unterprobleme als Basisfälle.
Combine the solutions zu den Unterproblemen in die Lösung für das ursprüngliche Problem.

Vor- und Nachteile des Divide and Conquer-Ansatzes

Der Divide and Conquer-Ansatz unterstützt die Parallelität, da Unterprobleme unabhängig sind. Daher kann ein Algorithmus, der unter Verwendung dieser Technik entworfen wurde, gleichzeitig auf dem Multiprozessorsystem oder auf verschiedenen Maschinen ausgeführt werden.

Bei diesem Ansatz werden die meisten Algorithmen unter Verwendung von Rekursion entworfen, daher ist die Speicherverwaltung sehr hoch. Für rekursive Funktionen wird ein Stapel verwendet, in dem der Funktionsstatus gespeichert werden muss.