Divide and Conquer

Divide and Conquer, auch lateinisch als Divide et impera oder auf deutsch als Teile und herrsche bezeichnet, ist ein Prinzip, auf dem viele Algorithmen basieren.

Die Idee

Um ein großes Problem zu lösen,

1. teilt man dieses in mehrere kleinere Teilprobleme
2. löst diese Teilprobleme und
3. führt die Lösungen zusammen.

Alltagsbeispiel

Wenn man einen bestimmten Eintrag aus einem alphabetisch sortierten Wörterbuch heraussucht, blättert man dieses nicht von vorne nach hinten seitenweise durch. Stattdessen schlägt man es an einer Stelle auf, wo man das Wort ungefähr vermutet und grenzt damit den Suchraum weiter ein.

Wenn ich zum Beispiel in einem Englisch-Wörterbuch das Wort furze suche, schlage ich das Buch irgendwo im ersten Viertel auf – der Buchstabe F ist der sechste von 26, also irgendwo im ersten Viertel – und lande vielleicht bei fickle. Ich bin schon mal bei F, muss also auf einer der nächsten paar Seiten fündig werden. Ich blättere etwas weiter und lande bei great tit – zu weit geblättert. Jetzt weiß ich aber ziemlich genau, in welchem Seitenbereich ich suchen muss, und kann das gewünschte Stichwort schnell finden.

Divide-and-Conquer-Algorithmen

Binäre Suche

Durchsuche ein sortiertes Feld, indem du das mittlere Element betrachtest. Dann weißt du, in welcher Hälfte des Suchbereichs du weitersuchen musst.

Mergesort und Quicksort

Sortiere eine Liste, indem du sie in zwei Teillisten unterteilst, die du rekursiv sortierst und dann wieder zusammenfügst