Das Mastertheorem

Mit dem Mastertheorem lassen sich Laufzeiten von Teilen-und-Herrschen-Algorithmen bestimmen, bei denen die Eingabe in eine feste Zahl (fast) gleich großer Teile aufgeteilt wird. Dabei gibt es drei Fälle zu unterscheiden, die man sich anhand einer "Chef vs. Mitarbeiter"-Regel merken kann: 1. Der Chef arbeitet mehr als seine direkten Mitarbeiter zusammen. Dann wird die Laufzeit von der Arbeitzeit des Chefs bestimmt. 2. Der Chef arbeitet weniger als seine direkten Mitarbeiter zusammen. Dann wird die Laufzeit von der Zahl der Blätter des Aufrufbaums bestimmt. 3. Der Chef arbeitet genauso viel wie seine direkten Mitarbeiter zusammen: Nun kommt die Höhe des Aufrufbaums mit ins Spiel; diese spendiert der Gesamtlaufzeit einen zusätzlichen log-Faktor. 00:00 - Intro 00:19 - Teilen und Herrschen (siehe auch    • Teilen und Herrschen  ) 04:04 - Rekursionsgleichung für die Laufzeit 15:18 - Fall 1: Chef arbeitet mehr 21:52 - Rechenbeispiel für Fall 1 22:58 - Fall 2: Chef arbeitet weniger 28:16 - Tiefe des Aufrufbaums 30:47 - Rechenbeispiel für Fall 2 31:51 - Fall 3: Cheff arbeitet gleich viel 33:18 - Rechenbeispiel für Fall 3 Einführung Teilen und Herrschen:    • Teilen und Herrschen   Beispiel für Fall 3: MergeSort:    • MergeSort