Video 7-5: Mergesort

0:02 Merch ist also bequem zu realisieren, indem man die Ausgabe woanders hinschreibt, als von wo man sie liest. In dem rekursiven Merchsort Algorithmus hätten wir es gerne aber so, dass man diesen Bereich hier gegeben hat und dann hinterher einfach dieser Teil sortiert ist. In meinen Bildchen hatte ich das ja dann immer so als aufsteigende Linie gemalt und äh ich möchte gerne, dass es das von außen so aussieht, als würde es das hier tun. Die Lösung dafür ist, dass wir intern die Daten zuerst woanders hinkopieren und dann zurückmergenchen in den Bereich, wo wir die Ausgabe tatsächlich gerne stehen hätten. Und äh im Code sieht das extrem kompakt aus. Der Code ist ein bisschen subtiler, als er vielleicht auf den ersten Blick scheint. Deswegen ähm werden wir eine Minute, um den zu besprechen. Der erste Teil ist einfach. Da mache ich genau, was ich eben äh angedeutet habe. Ich habe mein Array A gegeben. Das ist das Hauptarray, in dem wir sortieren oder das wir sortieren wollen. Und ich habe meine drei Positionen in diesem Array wie im Bild vorhin. Und ich habe aber auch noch ein Auxiliary Array, ein Puffer, ein äh Schmierzettel, auf dem ich Daten ablegen kann. Und die Annahme ist, dass die beide gleich groß sind.

1:20 Also beide haben Platz für alle Elemente. Was ich hier tue, ist aber nur den Bereich verwenden, der auch in A verwendet wird. Das ist äh für den letzten Merch dann eh das ganze kann ich mir also so erlauben. Das heißt, ich habe hier eine Schleife, die alle Elemente von A nach Aux kopiert. Danach sind die in beiden Arrays, aber ich kann sie insbesondere in A überschreiben. Und Merch selbst funktioniert dann so, dass ich mir zwei Positionen merke. Wie weit bin ich in diesen äh Runs, die hier sind, schon vorgekommen, schon vor schon voran vorangekommen? Sie sehen das hier unten als Beispiel in so einem Zwischenzustand. Diese grau ausm schraffierten Buchstaben, die sind sozusagen schon nicht mehr aktuell. Die habe ich äh schon verarbeitet. Die stehen natürlich trotzdem in dem Array noch drin, solange wir sie nicht überschreiben, aber die sind schon hier in der gemergten Ausgabe. Und die nächsten Elemente sind jetzt die ähm auf den I und J verweilen.

2:27 Und an der Stelle frage ich dann jeweils, na ja, einerseits ist i schon rausgelaufen, bin ich mit dem ersten Run schon ganz fertig, dann kann ich direkt vom zweiten Run kopieren von dem J. umgekehrt, falls J hier hinten rausgelaufen ist, dann ist der zweite Run aufgebraucht. Dann kann ich direkt aus dem ersten Run übernehmen und muss gar keinen echten Vergleich machen. Sehen sich das war dieser Fall, der auch im Beispiel vorkam, wo ich am die letzten paar Elemente vom zweiten Run einfach übernehmen konnte. Ansonsten mache ich den Vergleich, nämlich zwischen diesen beiden Elementen I und J. Und wenn jetzt das J echt kleiner ist, äh also das Element hier im zweiten Run echt kleiner ist als das Element hier im ersten Run, wie in diesem Beispiel MNO, M kommt vor, O im Alphabet, also wird äh das kleinere hier, das Jinkopiert.

3:24 Bei all diesen Dingen inkrementieren wir diesen diese Position in dem Array, die wir von der wir kopiert haben, um zu signalisieren, dass wir die schon verarbeitet haben. Das ist mit diesem äh Postkrement Operator sehr kompakt zu schreiben, ne? Es sind eigentlich zwei Operationen.

3:40 Der andere Fall ist symmetrisch, daüber nehme ich dann das I. Also, ich habe eine Schleife, die all diese Fälle abdeckt. Ähm, dass ich den ersten Run schon erschöpft habe oder den zweiten Run schon erschöpft habe oder keins von beidem. der normale Fall, den wir eigentlich am Anfang die meiste Zeit haben. Und dann habe ich die zwei Möglichkeiten, aus welchem Run das das nächst kleinere Element stammt, um jetzt noch mal zu schauen, ob sie am Start sind, wach sind, aufmerksam sind.

4:18 ein bisschen konkreter die Frage, sie dürfen da mehrere Antworten anhaken. Ähm, können also mehrere Sachen auch richtig sein. Und ich gehe dafür einfach noch mal auf den Code zurück. Sie haben ja die Frage auch auf den Geräten. M.

5:13 Uncool, aber wir waren auch später dran, haben nicht viel verpasst. Also lang langsam kommen die Ergebnisse rein. Das Ziel der Aufgabe ist natürlich auch sie so ein bisschen äh dahingehen zu triggern, dass sie über den besten und schlechtesten Fall nachdenken. Best Westcase.

5:58 Ich habe jetzt natürlich hier diese äh N und M tauchen jetzt mehrmals vor. In der der Slido Frage wäre n eben die Differenz zwischen mit und low Gut, noch jemand aktiv am Denken und tippen und abstimmen?

6:35 Sonst würde ich mal die Antworten zeigen. Also, der deutlichste Ausschlag ist natürlich hier bei diesem höchstens n + m. Wir machen höchstens so viele Vergleiche, wie wir Paarung von Elementen haben. Ähm schauen wir gleich im Code noch mal genauer drauf. Ähm viele der genau Antworten sind einfach zu streng, wenn man besten Worst Case anschaut. Die Frage ist, was ist der bestmögliche Fall? Und ähm das ist die letzte Antwort. Im besten Fall habe ich tatsächlich nur so viele Vergleiche wie der kleinere der Runs lang ist. äh schauen wir uns ganz kurz an, wie das zustande kommt. Ähm es sieht hier so aus, als könnte ich für jedes I und jedes J womöglich so ein Vergleich haben. Das aber nicht so, weil nach jedem Vergleich wird entweder I oder J eins größer und zwar auch genau eins, weder ähm mehr noch weniger. Das heißt, nach jedem Vergleich wandere ich entweder mit I oder mit J einen Schritt weiter durch das Array. Und sobald beide hier das Ende erreicht haben, höre ich auf mit den Vergleichen. Sobald einer das Ende erreicht hat, höre ich auf mit den Vergleichen. Also im schlimmsten Fall habe ich n + m für die Komplettlänge von diesem Arraystück.

7:56 Es kann mir aber auch passieren, dass die Arrays, dass die Vergleiche immer so ausgehen, dass das hier unterschiedlich lang ist, der Zeiger im kleineren Bereich, sagen wir mal, ähm n sei kleiner als m, dann könnte ich den Ausgang immer so haben, dass I gewinnt, also der der letzte Fall hier im Code. Dann würde ich n Schritte durch den Code machen. Danach muss ich trotzdem noch alle M Werte zurückkopieren in mein echtes Array. Aber ich mache dafür keine Vergleiche mehr mit mit diesem Less. An der Stelle ähm ist wichtig, ich sag jetzt immer Vergleiche gesagt, was hier konkret steht, ist der Aufruf von less. Der Unterschied ist, wir machen auch hier Vergleiche zwischen diesen Indizes, aber sie müssen bedenken, dass die wahrscheinlich deutlich unterschiedlich teuer sind. Dieser Aufruf hier, der vergleicht ja zwei Objekte aus unserem Array sortieren und das sind vielleicht, was weiß ich Universitäten, wo sie das Gründungsjahr nachschauen müssen. Das dauert während hier diese zwei Indizes vergleichen. Das sind ein Wort im Computer, das ist sehr schnell im Vergleich. Deswegen werden wir uns meistens drauf zurückziehen, diese Less Aufrufe zu zählen, weil die in der Praxis oft heute deutlich teurer sind als diese anderen Vergleiche.

9:16 ähm im Sprachgebrauch so ein bisschen bisschen ähm schwergängig, das immer sauber zu unterscheiden. Wenn man das möchte, könnte man sagen, die Lufrufe sind Schlüsselvergleiche, also Vergleiche zwischen den Schlüsseln, nach denen wir sortieren. Na gut, also das ist ähm Best and Worst Case für Merch. Daraus können wir auch mit sehr wenig Code den rekursiven Merch Sort bauen. Das folgt dem Muster, was wir am Anfang informell besprochen hatten. Wir haben die Merch Prozedur von der letzten Folie und dann habe ich ähm eine rekursive Prozedur, die einen Teil von A sortiert, nämlich von low bis high. Steht da nicht, aber es ist hier inklusive dem Endindex.

10:11 Und ähm da habe ich einen Rekursionsabbruch. Wenn high kleiner gleich low ist, hätte man auch sagen können, als ich habe höchstens ein Element in meinem Bereich, dann muss ich nichts mehr tun. Das ist schon sortiert. Ansonsten berechne ich diesen Mittelpunkt, indem ich im Wesentlichen den Mittelwert zwischen den beiden Dingern nehme. Wenn Sie sich fragen, warum das hier so seltsam geschrieben ist, ich hätte ja ähm vielleicht schreiben können high plus low und das ganze geteilt durch 2. Das ist vielleicht die natürlichere Weise, den Mittelwert zu berechnen. Das hat aber den Nebeneffekt oder den ärgerlichen Effekt. Wenn diese beiden sehr große Zahlen sind, dann könnte ich da ein integer Overflow generieren. Ich teil danach durch zwei, aber da ist der Overflow schon passiert. Wenn ich hier diese Differenz zuerst bilde, kann mir das nicht passieren, weil die Differenz ist nie größer als high und die Summe von den beiden ist auch nie größer als high. Das heißt, da geht nie was schief.

11:14 Sie erinnern sich außerdem ähm das geteilt durch 2 hier ist integer division, also mit Abrund, ne? Das heißt, wir bekommen hier immer ein Inufen dann unsere Prozedur auf rekursiv von low bis high. Das sortiert diesen ersten Teil und dann von mid + 1 von low bis mit, sorry, dann von mid + 1 bis high. Das sortiert den zweiten Teil und dann rufen wir unsere Merch Prozedur auf und alles passt genau wie wir es wie wir es äh vorgesehen haben. Das einzige, was noch ein bisschen unklar ist, wir haben dieses Auxiliary Array, was wir hier die ganze Zeit als als Parameter in der Rekursion durchreichen. Das ist vielleicht nicht die Variante, die an die Sie als erstes gedacht hätten. Das ist deshalb effizienter, weil man dann einmal am Anfang dieses Auxiliary Array allokieren kann und das dann in jedem Merchschritt wieder verwendet. Wenn sie stattdessen in jedem Merchschritt neu so ein Puffer anlegen würden, ist es deutlich teurer, weil diese Aufrufe, gib mir mal ein neues Stück Speicher ähm am Betrieb im Betriebssystem behältnismäßig teuer sind für diese vielen kleinen Merchschritte, die wir machen. Deswegen wird es hier durchgereicht, unverändert und immer nur innerhalb von Merch wirklich benutzt.

12:42 Ansonsten schauen sich den in Ruhe noch mal an oder äh versuchen mal ein paar Beispiele durchzuixen. Äh wir werden jetzt im weiteren im Wesentlichen über die Eigenschaften von diesem Code sprechen, nämlich die Performance. Ähm, der Code selbst ist relativ knapp, hat so ein paar Subtilitäten. Ich habe versucht ein paar schon aufzuzeigen. Äh, werden wir aber ansonsten dann jetzt nicht weiter im Detail äh drauf eingehen.

13:06 Also, wenn ihr noch Fragen einfallen, dann gerne auch noch nachschieben. Ähm, hier ist eine eine schöne Animation wieder von von Sechpick und Wayne übernommen, wo man sieht, was die verschiedenen rekursiven Aufrufe ausmacht. Also immer hier in ähm Fett gedruckt. Na ja, gut, die erste Zeile ist nur das ähm die Eingabe, aber hier in diesen Zwischenschritten Fett gedruckt ist der Teil, der dann durch den Merch überschrieben wird. Also das Ergebnis vom Verschmelzen dieser zwei Runs aus dem rekursiven Aufruf. Den rekursiven Abstieg sieht man in dem Bild nicht. Ich würde also anfangen mit hier gesamte Liste halbieren, aha, das rekursiv sortieren halbieren und so weiter. Passieren tut eigentlich wirklich erst was, wenn ich ganz unten angekommen bin bei einzelnen Elementen. Der erste Merch Aufruf hat dementsprechend hier auch, sehen Sie, äh nur zwei Elemente als Eingabe. Ein Run der Länge 1, ein zweiter der Länge 1 und die verschmelz dann eben. Ähm Ergebnis ist dann das EM.

14:09 Aus diesem rekursiven Aufruf für diese ersten vier Zeichen bekomme ich den zweiten rekursiven Aufruf für die rechte Hälfte. Auch der hat dann ein so ein Mini Merch mit den zwei Elementen. Davon steht das Ergebnis hier. Wenn ich aus den beiden rekursiven Aufrufen zurückkomme, dann verschmelze ich diese zwei Runs und deswegen ist dieser Teil hier fettgedruckt. Ich hoffe es ist klar geworden, wie das das Bild so zu lesen ist. Und man sieht dann eben hier die nächsten rekursiven Aufrufe und hat dann einen längeren Merch. Was man in dem Bild optisch, denke ich, einfach sehr schön sieht, ist da ist relativ wenig schwarz und ziemlich viel grau. Und grau heißt ja, da passiert eigentlich nichts und das kostet uns auch nichts. Das ist nur noch mal gemalt, damit wir besser nachvollziehen können, was passiert ist. Aber wir haben im Prinzip nur am Ende mal so ein paar große Zeilen, wo viel schwarz ist, wo wirklich die ganzen Elemente anfassen mussten. Äh wir verbringen sehr viel ähm sehr viel Teil ähm Schritte im Sortieren auf diesen kleinen Teilen, die uns auch nicht viel kosten. Das spricht so ein bisschen intuitiv für die Performance von Merch Sort. werden uns das natürlich gleich noch formaler angucken.

15:20 Ähm ein eine witzige Beobachtung, die ich Ihnen hier wieder in der Animation zeigen will, ist zumindest, wenn man ähm das so malt, wie hier.

15:38 Also hier die äh vier Eingaben kennen Sie noch, ne? Äh verschiedene Arten von Elementen, die man sortieren könnte bzw. wie die sich zueinander verhalten und ich mach's mal relativ langsam.

15:50 Sie sehen vielleicht am besten bei dem Reversed, wo die Rekursion gerade ist, ne? Das sieht man schön, den schon sortierten Teil und sie können es auch in den anderen Eingaben verfolgen. Was Sie insbesondere in dieser Animation sehen, äh ist, dass unsere Implementierung von Merchsord immer genau gleich viele Schritte macht in dieser Animation. Die ist in der Praxis nicht ganz immer exakt gleich schnell, denn wir hatten ja schon gesehen, Merch kann mal ein paar mehr Vergleiche, mal ein paar weniger Vergleiche brauchen. Da hier in dieser Animation aber gezeigt ist, wenn ich ein Array Element schreibe, ist das sozusagen weggebügelt. Sieht man nicht mehr. Äh, ich finde aber den Effekt hier trotzdem äh das ist dann auf der einen Seite lügt diese Animation ein kleines bisschen. In der Praxis haben sie ein bisschen Unterschiede in der Laufzeit, die von den Daten abhängen. Die sind aber relativ gering. Insofern ist die Lüge nur ganz klein und der Effekt, den man hier schön sieht, ist doch die eigentliche Wahrheit, dass im großen und ganzen der Großteil der Kosten unabhängig von den Daten ist.

16:56 werden wir gleich noch sehen, woher das ähm inhaltlich kommt. Äh erstmal hier noch so ein paar ähm absolute Zahlen. Äh ich habe es mir jetzt gespart, noch mal hier Tastatur auszupacken unds live laufen zu lassen. Äh sie werden etwas ähnliche Zahlen dann sehen und äh mit Livestream wie immer ein bisschen langsamer als sonst. Aber im Vergleich zu dem Insertion Sort, einem der besseren Verfahren aus dem letzten Kapitel, ist die äh Reduktion einfach ähm massiv. Ja, im Vergleich zu dieser äh ich nehme an, sie haben das nicht laufen lassen, sondern nur prognostiziert, ne? kommt man mit Merch viel viel schneller zum Ergebnis und wenn man vergleicht, was auf so einem Standard PC Laptop oder auf einem Supercuter passiert, dann ist der natürlich schneller, aber der richtig große Unterschied macht der bessere Algorithmus. Das ist ähm hatten wir schon drüber gesprochen in in dem Kapitel zum Argorithm Science, glaube ich, war es drin, dass die äh bessere bessere Hardware im Wesentlichen die den konstanten Faktor verbessern kann. Und das hier ist schon eine sehr ähm sehr optimistische Annahme, würde ich mal sagen. Aber die Algorithmen bestimmen eben die Skalierbarkeit oder das die Wachstumsrate und für große Eingaben ist das äh das, was dominiert.

18:30 Gut, Merchot scheint also gut zu funktionieren und wenig von den Daten abzuhängen. Es wäre doch irgendwie schön, wenn wir das analytisch begründen könnten, wenn wir das beweisen könnten und natürlich können wir das. Ähm, die Aussage hier ist, dass Merchsort höchstens n log n Vergleiche braucht, um N-Elemente zu sortieren. Und das ist unabhängig von der Eingabe. Das ist hier natürlich nur ein kleiner Gleich, das heißt, das lässt die ähm Abhängigkeit von den Daten noch ein bisschen offen. Wir werden aber gegen Ende vom Sortierkapitel sehen, dass da nicht so arg viel Luft ist. In den allermeisten Fällen ähm braucht man so viel und braucht Merchsort auch so viele Vergleiche mit einem ähm kleineren Fehler, einem groß von N, was das mal schwanken kann.

19:16 Merch ist ein rekursiver Algorithmus, das heißt diese Anzahl Vergleiche, die können wir bestimmen über eine Rekursion. Das ist hoffentlich nicht überraschend zu diesem Zeitpunkt. Wir haben also die Gesamtkosten, um Nelemente zu sortieren. Die setzen sich zusammen, die setzen sich zusammen aus den Kosten, um die linke und rechte Hälfte zu sortieren. Und da habe ich die Eingabe um etwa die Hälfte kleiner gemacht. Für beliebige N habe ich ärgerlicherweise dieses auf und abrunden. Das ist halt, was der Algorithmus tatsächlich tut. Wir werden uns dann auf für die Analyse auf zweier Potenzen für die Eingabegröße zurückziehen. Sie können dann am Ende immer ähm eine Abschätzung machen, dass jede jede Zahl ist ja höchstens zweimal kleiner als die nächste zweierpotenz und dann nehmen wir das als obere Schranke. Äh wenn ein nur das das Wachst die Wachstumsrate interessiert, dann reicht das. Ähm, wir haben also dann dieses auf und abrunden. Wenn man die zweier Potenzen nimmt, kann man loswerden und für den Merch nehmen wir den schlimmsten Fall an. Warum steht da jetzt nicht irgendwas wie n + m?

20:22 Äh n + m war die Länge der beiden Runs und die Länge der beiden Runs hier wären dieses n halbe auf und abgerundet, was sich immer zu n summiert. Also ich habe genau diese diesen Worstcase für die Anzahlvergleiche im Merchschritt. Das ist der Teil, den ich am Schluss für das Merchen bezahle. Kriegen also eine obere Schranke, deswegen steht hier auch kleiner Gleich ist eine Aussage für den Worst Case. Dann habe ich noch den Abbruch. Wenn ich nur ein Element habe, muss ich gar nichts sortieren, dann hat kostet das null. Äh mit der Vereinfachung für zweierpotenzen ähm hier jetzt eine andere ähm D genannt statt C, aber es ist identisch, ne? Wenn ich wenn ich da eine zweierpotenz habe, dann ist das auf und abrunden ohne Effekt. Dann habe ich diesen Aufruf zweimal. Das heißt, diese Art von Rekursion, die sollte Ihnen etwa bekannt vorkommen. Das ist genau, was wir für das Master Theorem hatten.

21:24 Und äh dementsprechend können wir ja noch einmal üben, wie man damit äh solche Rekursionen löst. Sie erinneren sich, es kommt im Wesentlichen auf diese Zahlen A und B an.

21:40 Das heißt, ich berechne dieses C und wie hoh mit welcher Potenz muss ich zwei Was ist die zweier die Potenz von zwei die zweier ergibt? Das ist halt gerade 1 und ich vergleiche demnach n hoch c mit diesen dieser Tollfunktion n mit den Kosten fürs Merchen. Das hier ist natürlich auch genau n. Das heißt, die die wachsen genau gleich schnell.

22:13 Das heißt, wir sind in diesem mittleren Fall, indem wir die das Wachstum von dieser Funktion haben mit einem log n Faktor dazu. Das wäre die Version mit dem Masterheorem. Die gibt uns diese Konstante vorne dran nicht ohne weiteres, ne? Das äh würde also noch nicht reichen, um diese diese Aussage zu beweisen. Aber ich denke, der Schritt zurück hier zum Master Theorem ist hilfreich.

22:59 An der Stelle lohnt es sich, wenn man die Konstante genauer wissen will, die Rekursion einfach direkt auszufalten. Das ist hier nicht besonders schwierig, deswegen hier einmal auf der Folie gemacht. Äh, wir haben den obersten Aufruf, der gibt uns n Kosten für das Merch. Dann habe ich zwei Aufrufe für die Hälfte der Eingabe. Die kosten jeweils n halbe, aber ich habe zwei davon. Das heißt, das summiert sich wieder zu n und das geht immer so aus. Ich habe zwei hoch i viele Aufrufe, wenn ich i Schritte nach unten gehe in dem Baum, aber jeder einzelne davon kostet mich auch nur n durch dur 2 hoch i, kürzt sich immer raus und ich habe immer Kosten, Gesamtkosten für die alle Merches auf einem äh auf einer Ebene der Rekursion von N. Und dann bleibt nur noch die Tiefe dieser Rekursion hier zu berechnen, aber steht da ja auch schon. Wie oft muss ich halbieren, bis ich bei 1 angekommen bin? Das ist gerade log n mal.

23:54 Dementsprechend bekommt man hier ähm diese Aussagen mit n log und wenn Sie es ganz formal wollen, dann machen Sie den Induktionsbeweis für die Ungleichung.

24:13 Auch der ist hier ausgeführt. Haben wir aber glaube ich oft genug geübt. Würde ich es nicht noch mal im Detail besprechen. Induktionsannahme einsetzen, rechnen und äh beobachten, dass die Aussage für das nächst größere für die nächst größere Zweierpotenz rauskommt.

24:36 Die Anzahl Vergleiche, die wir hier gezählt hatten, ist das eine. Wenn man in der Praxis Merchsort und sozusagen kleine kleiner Vorgriff auf das nächste Kapitel andere Sortieralgorithmen vergleichen will, dann ähm da stellt man fest, dass Merchsort zwar wenig Vergleiche braucht, aber dafür die Daten einige Male hin und her schaufelt. Äh wenn man z.B. die Anzahl Array Zugriffe zählt, also sowohl lese als auch Schreibzugriffe mit Kosten 1 zählt. Dann hat man einen Faktor 6, der kommt daher, weil ich zuerst das Kopieren habe. Also ich lese die Eingabe einmal, das ist ein N für ein Merch, dann schreibe ich es in das Aux auxiliary Array, das ist noch mal n. Dann lese ich es dort noch mal. Das sind drei und dann schreibe ich es noch mal zurück. Das sind vier. Ähm, aus einem Grund haben sie noch mal 2 N gefunden. Woher könnte das kommen? Müsste man sich das Merch noch mal anschauen.

25:41 Also, ich komme auf vier in meiner Zählung. Weiß nicht, ob ich da ähm gerade was übersehe, was offensichtlich ist. Merch Methode. Also, ich habe hier einen Zugriff fürs Lesen und hier fürs Schreiben. Umgekehrt lesen und schreiben. Umgekehrt hier wieder lesen und schreiben. Ah, die Vergleiche. Jeder Vergleich macht auch einen Array Zugriff. Das ist so ein bisschen, na ja, den hätte man sich den der ist wahrscheinlich im Cash. Den hätte ich nicht gezählt. Ähm, wenn man formal nur nach dem Code geht, stimmt das.

26:20 Lassen Sie mich nicht ähm über die Zahl zu sehr streiten, ob Faktor 4 oder Faktor 6 ist. Wir werden da was Besseres noch sehen, aber für den Moment halten wir fest, dass man auch diese Anzahl Array Zugriffe analysieren kann mit der gleichen Art von Rekursion. Alles was sich ändert ist, dass hier jetzt ja dieser Faktor 6 davor steht. Und für die mathematisch versierten ist offensichtlich, dass diese Rekursion linear in dieser Tollfunktion ist. Denn was was ich mit der Rekursion immer nur mache, sind rekursive Aufrufe aufadieren. Wenn ich also jeden auf jeden nicht rekursiven Teil um einen festen Faktor teurer mache, dann wird jeder von diesen rekursiven Aufruf um auch diesen festen Faktor teurer, weil alle bestehen am Ende aus Summen gewichteten Summen von diesen ähm nichtreursiven Teilen. Das heißt, aus der Warte ist offensichtlich, dass einfach das Ergebnis am Ende auch sechsfach größer wird. Aber man kann das auch natürlich mit der gleichen Art von Rekursionsbaum Idee nachrechnen. Dann habe ich hier überall eine sechs vorne stehen. Mehr passiert nicht.

27:30 Ähm, das lohnt sich so ein bisschen das im Hinterkopf zu behalten. Das ist ein typisches Muster, dass Sie wiedererkennen sollten, einfach um sozusagen die Analyse abzukürzen, wann immer sie so eine Struktur haben. Ich habe was, was lineare Kosten verursacht. Das mache ich als nichtrekursiven Teil und dann habe ich einen rekursiven Aufruf auf der Hälfte der Eingabe, aber für beide Hälften. Dann wird das Ergebnis immer n log n sein, weil ich immer das Masterthorem mit dem gleichen Fall B äh da zum Einsatz bringen kann. Und es gibt eine ganze Reihe von Algorithmen, wo jetzt nicht wichtig ist, ähm was da genau dahinter steckt, die eben auch genau diese Struktur haben. Так.