Divide and Conquer
Divide and Conquer ist eine beliebte Methode, um algorithmische Probleme zu lösen. Wir haben bereits einige Techniken kennengelernt, um algorithmische Herausforderungen zu bewältigen. Bei einem Greedy-Ansatz wird in jedem Schritt die lokal optimale Lösung gewählt. Bei der Dynamischen Programmierung wird der aktuelle Zustand auf Grundlage der vorherigen Zustände aufgebaut. Beim Divide-and-Conquer-Prinzip hingegen unterteilt man das Problem in kleinere Teilprobleme, löst jedes davon einzeln und kombiniert anschließend alle Ergebnisse. So teilen wir das Problem in Teilprobleme und erobern (conquer) das Ausgangsproblem durch das Zusammenführen der Teillösungen.
Challenge
Stell dir vor, du hast 512 Zahlen und ebenso 512 spezialisierte Computer (sehr kleine Spezialcomputer), die jeweils nur zwei Zahlen entgegennehmen und den größeren Wert zurückgeben können.
Dein Ziel ist es, mit möglichst geringem Zeitaufwand das Maximum unter diesen 512 Zahlen zu ermitteln.
Jeder dieser Computer kann zwei Werte empfangen und innerhalb von 1 Sekunde den größeren der beiden Zahlen berechnen und ausgeben (ja, sie sind ziemlich langsam 🐌). Kannst du dir eine Vorgehensweise überlegen, mit der du so schnell wie möglich das Maximum aus allen Zahlen ermitteln kannst?