Teile und Herrsche 1 SS10
Aus ProgrammingWiki
Archivierte Version vom 2010-04-06T12:46:31+00:00. Aktuelle Version
Inhaltsverzeichnis |
Autoren:
- Raffael Thomas Lang (siralang@stud.hs-zigr.de)
- Sebastian Kramer (sisekram@stud.hs-zigr.de)
Was ist überhaupt Divide and Conquer?
DaC (eng. "Divide and Conquer") auf deutsch "Teile und Herrsche" genannt und in lat. "divide et impera". Es beschreibt folgendes Vorgehen bei Problemen:
- zerteilen des Problems in Teilprobleme (divide)
- lösen der einzelnen Teilprobleme, mittels rekursiven Aufruf (conquer)
- Teillösungen zusammenführen zu der Gesamtlösung (konkatenieren)
Das schnelle Sortieren
sqrt(5 + 5)quicksort
Sortieren durch mischen
mergesort