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 https://youtu.be/jFZtAD8ePYk)
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: https://youtu.be/jFZtAD8ePYk
- Beispiel für Fall 3: MergeSort: https://youtu.be/pmwcid74WDQ