Divide and Conquer

Das Divide and Conquer Prinzip in der Informatik

Das Teile und herrsche Prinzip findet in der Informatik besonders in der Gestaltung von Such- und Sortieralgorithmen eine große Rolle. Das Prinzip bietet einen reduktionistischen Lösungsansatz an.

Das Grundprinzip sieht folgendermaßen aus:

Das ursprüngliche Problem wird in kleinere, simplere Probleme aufgeteilt. Jedes dadurch entstandene Teilproblem wird wiederrum in kleinere Teilprobleme aufgeteilt. Dies geschiet so lange, bis das Teilproblem gelöst werden kann. Das Teilproblem wird gelöst. Dies geschieht für jedes Teilproblem. Am Schluß werden alle Teillösungen zusammengeflochten. Dabei entsteht eine Lösung des ursprünglichen Problems.