Video 3-7: Das Master-Theorem

0:04 Im nächsten Abschnitt also das Master Theorem, großer Name für eine Methode, mit der manche Rekursionsgleichung nach einem festen Schema lösen kann. Äh, die Motivation dazu kommt von einem Sortieralgorithmus und wir haben natürlich darüber noch gar nicht gesprochen. Das heißt, das ist absolut nicht äh meine Erwartung, dass Sie das schon kennen. Wir werden darüber auch noch ganz in Ruhe und im Detail in paar Wochen sprechen. für die Motivation, warum wir uns diese Arten von Rekursionsgleichung anschauen, möchte ich aber diesen Algorithmus zumindest erwähnen. Und falls fast alle von ihnen den schon kennen sollten, dann werde ich ein zwei Takte dazu sagen. Ähm falls nicht, dann ähm würde ich das vertagen und würde sozusagen einfach nur sagen, da kommt eine Motivation noch. Wir schauen uns jetzt erstmal nur die Mathte dahinter an.

1:09 sieht mir auch so ein bisschen nach der Richtung aus. Ich will sie natürlich jetzt nicht beeinflussen. Wenn ich jetzt zeige, was so abgestimmt wird, dann verfält ich glaube ich die Abstimmung.

1:49 Okay, als als halbwegs repräsentatives Sample ähm lassen es uns mal dabei belassen. Also ein signifikanter Anteil weiß noch nicht äh was Merch was mit Merch Merch Sort auf sich hat. Ähm ja, im Prinzip kann ich Ihnen das auch sagen. Äh diese zweite Antwort ist das, was ähm sich hinter Merchort verbirgt. Wie gesagt, mein Punkt ist nicht, dass sie das jetzt wissen müssen. Die Frage war, wie sehr gehe ich darauf ein, woher diese Rekussionsgleich kommt? Ähm Merch ist ein Beispiel für Divide and Conquer Algorithmen, also Algorithmen, die nach einem festen Schema Fall von Merchsort, nämlich wie folgt. Es gibt eine Eingabegröße N, ähnlich wie bei den Türmen von Hanneu. Wenn das N ganz klein ist, dann habe ich direkt äh nichts mehr zu tun. Ansonsten teile ich meine Eingabe in zwei gleichgroße Teile auf. Also zwei Teile der Größe n durch 2. Und auf diesen beiden Teilen rufe ich rekursiv auf die gleiche Methode, mit der ich das Gesamtproblem löse. In dem Fall ähnlich wie die Türme von Hanneo, aber der Aufruf hier ist mit n ge 2, nicht n - 1. Und das macht für die Laufseiten riesen Unterschied.

3:11 Ich habe dann noch den letzten Schritt, dass ich diese Lösung, die ich aus dem Teilproblem bekomme, aus den beiden Teilproblemen bekomme, noch zu einer Gesamtlösung wieder äh kombinieren muss. Und der Teil ist der Teil, der dann auch Kosten verursacht.

3:26 Also was dahinter steckt und was das im Detail mit sortieren zu tun hat, dazu kommen wir. Für heute äh ist das irrelevant. Ähm wenn man sich die Laufzeit von so einem Verfahren anschaut, ganz ähnlich zu den Türmen von Hannoi, dann habe ich eine Laufzeit für die Größe N. Das ist entweder in dem Fall gar nichts, wenn ich eine kleine Eingabe habe, da muss ich genau nichts tun. Kommt drauf an, was man hier zählt. Wir äh bei Merch würde man sowas wie Vergleiche zählen oder so. Ähm kommen wir noch dazu. Ist jetzt nicht so wichtig. Rein mathematisch ist einfach eine Definition, wenn Sie mögen. Äh für größere Eingaben habe ich zweimal den Aufruf auf der halb so großen Eingabe und ich habe noch diesen kombinieren Aufwand. Können Sie mir jetzt erstmal glauben ist einfach ein +. Diese Art von Rekursionen möchte man also gerne lösen, weil sie die Laufzeit von relevanten Algorithmen beschreiben.

4:23 Eine Option wäre, man setzt die mal ein und guckt, was so passiert und hofft, dass einen irgendwie äh ein Geniestreich trifft und man die Lösung sieht. Wenn das nicht funktioniert, dann gibt's in diesem Fall eine etwas systematischere Methode, ähm, die so ein bisschen mit dem Einsätzen zu tun hat. Den Teil muss ich jetzt etwas knapp machen, aber ganz ganz kurz das Bild dazu.

4:54 Also, wie würde das Raten aussehen? Ähm, ich male eigentlich immer diesen lillanen Teil. Der erste Aufruf verursacht Kosten n und diese rekursiven Teile. Also die Kosten n hier sind vom ersten Aufruf. Dann habe ich zwei Aufrufe auf der Hälfte dieser Eingabe. Aus der Hälfte habe ich jeweils wieder dieses + n.

5:25 Das heißt, auf dem von den zwei Aufrufen, die ich da mache, habe ich zweimal n halbe. Das ist aber wieder n. Und dann würden jeder diese Aufrufe ja wiederum die Eingabe halbieren und zwei Aufrufe generieren, die sich auch in Summe wieder zu nmieren, aber ergeben sich eigentlich als 4 x n dur 4.

5:54 Und so könnte ich weitermachen. Jetzt muss ich nur irgendwann auch aufhören. Und wann höre ich auf? Na ja, wenn ich einzelne Elemente habe, denn dann bin ich in diesem Basisfall. Vielleicht sollte ich die in orange malen.

6:08 Also irgendwann bin ich hier unten, sodass dieses letzte Level nur einzelne Elemente sind. Das sind aber auch äh nstück, weil in diesem Halbieren geht nie was verloren. Was ich jetzt noch nicht geklärt habe, ist wie viele von diesen Schichten habe ich? Das ist eine allgemeine Methode. Mit diesen Arten von Bildchen kann man solche Rekursionen halb halbwegs systematisch lösen, aber es ist ein bisschen ähm bisschen mühsam und im Detail manchmal nicht ganz so einfach wie das hier in diesem äh wohlgewählten wenig fiesen Beispiel funktioniert. Deshalb gibt's ein allgemeines Lösungsverfahren für diese Art von Rekursion. Das allgemeine Verfahren, also das allgemeine die allgemeine Form von solchen Divide in Conquerre Rekursionen hat nicht nur zwei rekursive Aufrufe, sondern eine beliebige Anzahl A. Die Teil Probleme haben nicht die Größe n durch 2, sondern n durch b für irgendeine Zahl b. Der Aufband, um die Lösung zu verschmelzen, ist irgendeine Funktion f nicht unbedingt n. Und der Basisaufall, wenn ich also in dem kleine kleinste Eingaben habe, der war bei uns null, der könnte irgende eine andere Konstante sein. Das ist das allgemeine Schema. Dann ist das die Rekursion, die sieht, hab das ja hier noch kopiert, was so aus wie die Merch Sort Rekursion. Ich habe mich bemüht, das mit den passenden Farben zu malen, ja, dass Sie die Entsprechung sehen. Äh ist also eine Instanz davon wäre diese Merchsort Rekursion, aber das ist natürlich allgemeiner.

7:47 Für diese Art von Rekursion gibt's eine eine Hautraufmethode, die für viele dieser Lös dieser Rekursion direkt eine Lösung liefert, zumindest in im Sinne einer Thetasse. Was man tun muss ist eine eine bestimmte Zahl berechnen, nämlich dieses C, der Logarithmus zur Basis B von A. Das hat so ein bisschen was damit zu tun, wie viele Levels ich in dieser Rekursion habe. Ähm Intuition schieben ander mal dann noch nach. Abhängig von diesem C gibt's drei Fälle und je nachdem, welcher dieser Fälle eintritt, ist die Lösung eine andere. Was ich immer vergleiche ist das C hier als Exponent mit dem Wachstum meiner Funktion f. Also, wenn f deutlich langsamer wächst als n hoch c, brauche ich n hoch c- irgendeine kleine Zahl n hoch c - 0,1 oder so. Wenn ich das zeigen kann, dann habe ich eine Lösung für meine Rekursion. Wenn ich das hier zeigen kann, meine Funktion f ist etwa gleich groß wie das n hoch c, dann habe ich diese Lösung.

9:02 Und wenn meine Funktion f deutlich schneller wächst als dieses N hoch c, dann habe ich eine dritte Lösung. In diesem letzten Fall brauche ich aber noch so eine eine technische Bedingung für meine Funktion f, diese Regularitätsbedingung, weil das sonst nicht immer im Allgemeinen nicht funktioniert.

9:22 Die Intuition hinter dem, warum macht das Sinn, dass das hier rauskommt, die machen wir nächstes Mal am Montag noch mal im Detail. Damit Sie aber für die für den nächsten Übungszettel zumindest das Theorem schon gesehen haben, wollte ich das auf jeden Fall schon mal vorab einstreuen. Gleich noch zwei Kommentare dazu, wie man sich um dieses Prüfen der Regularitätsbedingung meistens drücken kann. Und für den Moment glauben Sie einfach mal, dass das Theorem so Sinn ergibt. Warum das intuitiv Sinn ergibt, will ich noch ein bisschen ausfühlen, aber das muss man auf Montag vertagen.

10:04 Die Regularitätsbedingung ist im Allgemeinen nötig, aber für viele Funktionen, nämlich alles, was irgendwie gebaut ist als n hoch eine Zahl, eventuell noch mal log hoch irgendwas, gilt diese Regularitätsbedingung immer, wenn ich wenn mein Better groß genug ist. Und das ist genau das, was man eh braucht. Also für den typischen Fall von Rekursionsgleichung, der Ihnen auch meistens begegnet, brauchen Sie das hier gar nicht von Hand nachrechnen und diese Konstanten finden, weil die Funktion von dieser Form die immer erfüllt. Okay, das wollte ich Ihnen noch mitgeben. Den den Rest machen wir am Montag in Ruhe.

10:54 Sie können also mit diesem mit diesem Master Theorem Rekursion von diesem Schema systematisch lösen, sofern sie eine dieser Bedingungen erfüllt. Es gibt Fälle von Rekursionen, die diesem Schema folgen, in denen das Masterthorem keine Aussage liefert, weil z.B. keiner dieser drei Fälle eintritt. Die sind nicht allumfassend. diese Decken drei Teile ab, aber da gibt's noch was dazwischen.