Das Teile-und-herrsche-Verfahren (englisch divide and conquer bzw. lateinisch divide et impera) bezeichnet in der Informatik ein Paradigma für den Entwurf von effizienten Algorithmen.
Der Grundsatz findet unter anderem Anwendung in Such- und Sortierverfahren.
Bei einem Teile-und-herrsche-Ansatz wird das eigentliche – in seiner Gesamtheit – als zu schwierig erscheinende Problem so lange rekursiv in kleinere und einfachere Teilprobleme zerlegt, bis diese gelöst („beherrschbar“) sind. Anschließend wird aus diesen Teillösungen eine Lösung für das Gesamtproblem (re-)konstruiert.
Die Binäre Suche nach einem Schlüssel ist eine der ersten algorithmischen Anwendungen des Prinzips von „teile und herrsche“. Sie lässt sich zu den Babyloniern zurückverfolgen. Bei der binären Suche wird ein Schlüssel in einer sortierten Schlüsselmenge gesucht. Dazu vergleicht man den gesuchten Schlüssel mit dem Median der Schlüsselmenge und sucht dann entsprechend in der Teilmenge der Elemente kleiner als der Median oder in der Teilmenge der Elemente größer als der Median rekursiv weiter.
Der Euklidische Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen folgt ebenfalls dem „Teile-und-herrsche“-Prinzip. Hierbei wird das Problem iterativ vereinfacht, indem man „gemeinsame“ Teile entfernt.
„Teile und herrsche“ ist eines der wichtigsten Prinzipien für effiziente Algorithmen. Dabei wird ausgenutzt, dass bei vielen Problemen der Lösungsaufwand sinkt, wenn das Problem in kleinere Teilprobleme zerlegt wird. Dies lässt sich meist durch Rekursive Programmierung umsetzen, bei der die Teilprobleme wie eigenständige Probleme gleichzeitig parallel oder sequenziell (einzeln nacheinander) behandelt werden, bis sie auf triviale Lösungen zurückgeführt sind oder der Restfehler hinreichend klein ist. Bei manchen Algorithmen steckt dabei die Kernidee im Schritt des „Teilens“, während die „Rekombination“ einfach ist (beispielsweise Quicksort). In anderen Verfahren (beispielsweise Mergesort) ist das Teilen einfach, während die Rekombination die Kernidee des Algorithmus enthält. In manchen Algorithmen sind beide Schritte komplex.
Die Lösung für das Gesamtproblem ergibt sich je nach Algorithmus auf verschiedene Weise. Möglichkeiten sind unter anderem:
In vielen Programmiersprachen wird die Gliederung von Computerprogrammen in Prozeduren, Funktionen, Module, Objekte, Komponenten, Prozesse und Threads nach dem Prinzip „Teile und herrsche“ umgesetzt.
Die Methode „Teile und herrsche“ lässt sich auch für Probleme nicht-mathematischer Fachbereiche und im Alltag anwenden. Man zerlegt ein schwieriges Problem in kleine Teilprobleme, die man dann einzeln lösen und zu einem Gesamtergebnis zusammenfügen kann. Wer beispielsweise ein Buch schreiben will, kann eine Skizze als Gerüst verfassen, dann jede Komponente einzeln angehen und abschließend alles zu einem zusammenhängenden Werk zusammenfügen.[1]