Video 7-9: Untere Schranke fürs Sortieren

0:03 Im nächsten Abschnitt schauen wir uns eine untere Schranke fürs Sortieren an. Untere Schranke heißt an der Stelle ein Unmöglichkeitsresultat, sprich ein mathematisches Theorem, das ihnen sagt, besser als mit diesen und jenen Kosten kann man dieses algorithmische Problem nicht lösen. Wir werden das hier insbesondere natürlich fürs Sortieren machen, aber sie sollen daraus zwei Dinge mitnehmen. Einerseits ist es ein ganz großartiges Feature der Informatik, dass wir solche Ergebnisse haben und dass diese Ergebnisse oft auch nahe an einer oberen Schranke liegen, also an einem konkreten Algorithmus, der ein Problem auch löst. Wenn ich also einen Algorithmus habe, der eine bestimmte Anzahl Kosten hat und eine untere Schranke, die sagt, besser als diese und jene Kosten geht's gar nicht und diese beiden Werte nahbeinander liegen, dann ist der Algorithmus in einem gewissen Sinne bestmöglich. Das ist das erste. Das ist also die die positive Message ist, es ist unglaublich stark, wenn man solche Unmöglichkeitsresultate hat und die wenigsten Disziplinen haben welche, die so nah an das Mögliche ranreichen äh wie in der Algorithmik. Deswegen ist das ein großer Bonus, den wir haben. Auf der anderen Seite, wann immer ihn jemand was verkaufen will, als dass es ein optimaler Algorithmus, eine optimale Lösung für dies und jenes Problem, sollen Sie instinktiv sagen, optimalbezüglich was, denn das ist fast immer ein bisschen, es ist fast immer äh eine Lüge und es braucht immer eine Einschränkung.

1:33 Ähm, ich werde Ihnen genau sagen, in welchem Sinne es hier keine Lüge ist. Ich lüge sie natürlich nicht an, aber man muss präzise formulieren, damit es keine Lüge wird. Und umgekehrt kann man aus der genauen Formulierung auch ablesen, wie man vielleicht diese untere Schranke umgehen könnte. Dazu dann gleich mehr. Jetzt noch mal zurück zu diesem zu diesem Ratespiel, dass ich eben schon äh gezeigt hatte, weil man doch vielleicht ein paar Minuten braucht, um darüber nachzudenken. Ähm, wir schauen uns gleich die Antworten auch an. Ähm, noch mal, also ihr Partner denkt sich eine Zahl zwischen 1 und 100 aus. Es gibt also 100 verschiedene Möglichkeiten, keine Psychospielchen. Wir wissen nicht, dass da immer 77 rauskommt oder irgendsowas. Ähm und uns interessiert deswegen hier das Schlüsselwort mit wie vielen ja nein Fragen geht es immer. Uns interessiert sozusagen der Worst Case. Wenn Sie mögen, können Sie sagen, sie Sie denken sich ihre geheime Strategie aus. oder nicht so geheim und sie können sogar die Strategie, wie sie Ratenwerten ihrem Partner mitteilen und danach wählt ihr Partner die schlechteste der Zahlen aus.

2:45 Das ist natürlich so ein bisschen ähm da müsste der Partner auch mitspielen, aber sozusagen ähm im im schlimmsten Fall ist das, was ihnen passieren kann. Selbst wenn Sie ihre Strategie, wie Sie diese Fragen stellen werden, offenbaren müssen, können Sie garantieren mehr als so und so viel Fragen brauche ich nicht. Na gut. Ähm, schauen mal kurz auf die Antworten und dann wollen wir das natürlich auch kurz auflösen.

3:16 Also, sehr gute Verteilung. Ähm, sind auch ein paar richtige Antworten dabei. Es sind auch sehr viele Antworten dabei. Das ist auch immer spannend. Also, die richtige Antwort ist 8. Präzise zählt.

3:29 Ähm, dazu ganz kurz. Was der der Tipp war, den ich ihnen gegeben hatte, war angenommen, wir machen das mit einem kleineren Universum als mit mit 100. Und das kleinste, na ja, das kleinste, was von der Definition her Sinn macht, ist, wir haben nur ein Element. Dann sollte ich keine Frage brauchen, um zu wissen, welches Element es ist. Aber ich zähle ja diese Gewinnfrage mit. Das heißt, für ein Element muss ich trotzdem eine Frage stellen.

4:08 Also, ich gewinne sozusagen erst, wenn mein äh wenn ich so eine ist gleich Frage gestellt habe und mein Partner gezwungen wurde, ja zu antworten. Ähm, wenn ich zwei Elemente habe, das ist jetzt wirklich der erste nicht komplett bescheuerte Fall, dann habe ich die ein und die zwei und wie ich mich drehe und wende, ich werde nicht mit einer Frage auskommen. Wenn ich Glück habe, kann ich kann ich direkt fragen, ist deine Zahl die ein und vielleicht habe ich Glück, aber sicher heißt ja, ich muss mit dem Pech ähm zurechtkmen. Das heißt, hier werde ich zwei Fragen brauchen und da gibt's natürlich verschiedene Optionen. Ich könnte z.B. Fragen ist es die ein und wenn die Antwort nein war, dann sage ich dann ist es die zwei. Richtig. Das ist eine Option. Ich könnte aber auch fragen, wenn ich mir vorstelle, ich teile die Zahlen in eine kleinere und eine größere Hälfte, ist die Zahl in der linken oder in der rechten Hälfte von diesen beiden Zahlen?

5:01 Also ist die Zahl kleiner gleich 1. Ist natürlich hier jetzt für zwei Zahlen kein Riesenunterschied, aber ich könnte mir z.B. will als nächsten Fall drei Zahlen anschauen. Machen wir erstmal vier. Habe ich 1 2 3 und 4. Und da macht's erstmal ein Unterschied, welche erste Frage ich zum ersten Mal macht hier ein Unterschied, welche erste Frage ich stelle. eine clevere wäre in der Mitte wieder zu halbieren. Also ist die Zahl kleiner als 2,5 wäre auch erlaubt. Wir haben ja beliebige Jaheninfragen zugelassen.

5:35 Das heißt nach einer Frage habe ich den Fall reduziert auf U = 2. Und da weiß ich schon, ich brauche zwei Fragen, also sind insgesamt drei. Dann kann ich mir überlegen für drei, egal wie ich mich drehe und wende, ich werde nach einer Frage mit im schlimmsten Fall immer noch zwei möglichen Antworten übrig bleiben. Das heißt, auch in diesem Fall kann ich mit einer Frage das auf den Fall u = 2 reduzieren. Und dann erkennt man vielleicht das Muster, dass man in am besten immer in der Mitte halbieren will. Also habe ich eine Frage, am Anfang habe ich 100 Möglichkeiten. Nach einer Frage mit Hälfte habe ich noch 50, dann 25 13 7 4 2 1 und dann habe ich gewonnen. Also brauche ich eine Frage. 2 3 4 5 6 7 8.

6:38 Mit der achten gewinne ich dann. Da habe ich nur noch eine Möglichkeit gehabt. Ja. Also die die Fragen sollte ich hier zählen. 1 2 3 4 5 6 7. Nach 7 weiß ich schon, welche Zahl es ist, aber ich muss diese Gewinnfrage noch stellen. Okay, kann man natürlich jetzt auch noch allgemein ausrechnen, was da für beliebiges U dann die der Wert ist. Äh darum geht's mir jetzt aber gar nicht.

7:13 Also zurück zur Motivation. Wir haben zwei Sortierverfahren kennengelernt, Merch und Quicksort, die beide dieses NLOG endn Verhalten hatten. Bei Quicksort nur in Erwartung, aber ja doch irgendwie die meiste Zeit, ist es Zufall, dass die beide sich auf diesen Wert n log einpendeln oder steckt da was dahinter? Und ähm weil es kein Zufall ist oder wie auch immer die erste Frage ausgeht, kann ich es denn noch schneller? Und die Antwort ist nein, ähm zumindest mit gewissen Einschränkungen. Und äh um dem die gebührende Breite zu geben als Theorem ausformuliert. Das heißt dann auch die Informationstheoretische Untertchranke fürs sortieren, weil wir im Wesentlichen über die Information argumentieren, die ein Sortieralgorithmus lernen muss über die Eingabe, damit er sie sortiert haben kann. werden sie gleich sehen. Und das ist natürlich das, was auch mit diesem äh Puzzle passiert. Ich habe nicht drüber argumentiert, wie lange ich denken musste, bis meine nächste Frage gestellt wurde, sondern ich habe nur argumentiert, was ich über die möglichen Zahlen schon gelernt habe.

8:20 Also das konkrete Resultat heißt aber jeder vergleichsbasierte Sortierealgorithmus benötigt den Worst Case um Nelemente zu sortieren, mindestens Logarithmus von n Fakultät aufgerundet, was sich asymptotisch darstellen lässt als n log n - n log zur Basis 2 von n - ein linearer Term, den man ausrechnen kann und noch ein bisschen zerquetschte, die uns selten interessieren. Daraus folgt sofort: Merchort ist im Wesentlichen bestmöglich. Ja, also auch Quicksort, aber Merchsort noch mehr, weil Merchsort hatte auch diesen führenden Termlogen mit genau dieser Konstante. Also, da ist dann nur noch dieser zweite Term übrig als Spielraum.

9:11 Wie soll man aber jetzt so ein Resultat beweisen können? Erstens ist es ja ähm wie ich angeteasert hatte, ein starkes Resultat, denn jeder Algorithmus, das heißt ja für alle Algorithmen gilt Doppelpunkt. Wie soll man das beweisen? Wie soll ich alle möglichen Algorithmen abdecken können? Und da kommt dieses Vergleichsbasiert ins Spiel. Man muss für so eine Aussage immer ein Maschinenmodell haben, mit dem man irgendwie arbeiten kann und erstmal formalisieren kann, was das überhaupt heißt, alle Algorithmen. Deswegen hatte ich sie auch schon an eingangs in der Vorlesung mit diesen Maschinenmodellen ein bisschen länger gequält. Wir hatten damals dieses Word RAM Modell z.B. uns angeschaut. Das ähm könnte man theoretisch als Modell nehmen und versuchen so ein Ergebnis zu beweisen. Das ist aber viel schwieriger und auch in dem Fall nicht ganz klar. Also fürs sortieren in Wordram ist es ein offenes Forschungsproblem, was die beste Komplexität ist. Werden wir also nicht machen. Ähm stattdessen schauen wir uns ein stärker eingeschränktes Maschinenmodell an. Das heißt, wir erlauben nicht alle Algorithmen, die für irgendwie eine unser theoretisch mächtigstes Modell Sinn machen, sondern nur ein eingeschränktes.

10:22 Und das sind eben diese vergleichsbasierten Algorithmen. Was das konkret heißt, ist, ich darf auf meine Eingabe, die immer in einem Array vorliegt, genau nur über diese zwei Operationen zugreifen, die wir auch für die Algorithmen schon verwendet haben. Also, ich darf nur fragen, ist Position I kleiner als Position J und darf dann abhängig von der Ausgabe was tun und ich darf Elemente vertauschen. Man kann so ein bisschen aufweichen zu so wie Merchort oder manche der anderen Algorithmen. Ich darf auch Schreib und Lesezugriffe auf dem Array machen, die kann ich theoretisch mit Swaps auch simulieren. Das ist nicht der wichtige Punkt. Äh, der wichtigere Punkt ist, dass ich nur über less etwas über die Eingabe lernen kann, über die Elemente. Das ist also im Wesentlichen für alle unsere Sortieralgorithmen eh schon der Fall mit sozusagen leichten äh Änderungen, damit wir wirklich nur Swaps verwenden. Quicksot z.B. direkt nur Swaps. Äh, das heißt, es ist keine Einschränkung. Alle diese Algorithmen, die wir bisher gesehen haben, fallen unter diese Kategorie vergleichsbasiert.

11:29 Und das heißt implizit, wir dürfen keinerlei Annahmen an die Eingabetpen treffen. Welche Objekte wir da sortieren, soll offen und sozusagen äh egal sein für unseren Algorithmus. Okay, ein Maschinenmodell muss immer zwei Dinge festhalten. Das muss sagen, welche Algorithmen gibt es und was kostet eine Ausführung. Und hier machen wir nur die Anzahl Aufrufe an L, also die Anzahlvergleiche. zum zum Maß aller Dinge. Äh, das heißt, alle andere Berechnung ist umsonst. Das ist natürlich unrealistisch, aber das ist hier besser, denn wir machen eine untere Schranke, ein Unmöglichkeitsresultat. Wenn ich also schon keinen Algorithmus finden kann, der nur in diesen diesem einen Kostenmaß günstiger als dieses Nlogin ist, dann auch in Gesamtkosten nicht. Das ist ja dann nur noch mehr.

12:26 Und jetzt kommt der erste die erste nicht triviale Beobachtung aus dieser Definition, dass wir nur über Vergleiche auf die Eingabe zugreifen. Ich kann meine Algorithmen in diesem vergleichsbasierten Modell auf ein theoretisches auf eine theoretische Normalform bringen. Klammer auf, das ist nicht wie wir Algorithmen schreiben wollen, um sie in der Praxis schnell zu machen. Das geht nur dann bequem, wenn wir tatsächlich nur Vergleiche zählen wollen. Aber das ist eben der Fall. Wir machen das hier für den für den Beweis nicht als Designmuster für Algorithmen.

12:59 Für jeden vergleichsbasierten Algorithmus kann ich so tun, als mache ich erstmal alle Vergleiche und alle Swops verschiebe ich ans Ende des Algorithmus. Dafür muss ich mir die Ergebnisse von all diesen Vergleichen merken. Und ich muss auch sozusagen vorweg simulieren, wenn der Algorithmus sonst Vergleiche gemacht hätte und abhängig davon ein paar Swaps und dann wieder Vergleiche, dann sind die Indizs, mit denen er jetzt vergleicht, nicht mehr die Originalen. Aber rein theoretisch kann ich zurückrechnen und mir überlegen, in den Originalinds, welche Vergleiche wären das denn gewesen, wenn ich den Swap nicht gemacht hätte? Das ist so die Idee, die wir hier verfolgen. Also, wir machen alle Vergleiche zuerst. und danach alles andere. Was das aber heißt, ist, dass all die Swaps im Wesentlichen blind erfolgen. Ich gucke nicht mehr auf die Eingabe. Ich habe mir einfach schon vorher überlegt, genau dies Vertauschung muss ich jetzt machen und ich lerne nichts Neues mehr über die Eingabe. Das gesamte Wissen über die Eingabe, insbesondere die Reihenfolge, liegt nach den Vergleichen vor und ich lern danach nichts Neues mehr.

14:01 Okay, das ist diese Normalform und diese Normalform hat den großen Vorteil, dass man sie grafisch darstellen kann als einen solchen Entscheidungsbaum ähm der auch jetzt tatsächlich nur die Vergleiche zeigt. Alles andere vom Algorithmus ist eh umsonst. Das ignorieren wir also komplett. Also ein Entscheidungsbaum ist so ein Baum, der diese Knoten hier hat. Jeder einzelne Knoten ist ein Vergleich. Da frage ich also ist die das Element dann Position 0 im originale Rayen sich keine Vertauschung. Ist Position 0 im original kleiner als Position 1 imAray? Ja. Nein. Ähm da gibt's zwei Möglichkeiten. Entweder ja oder eben nein. Und die führen dann zu einem potenziell weiteren Vergleich. Und das muss ich so lange machen, bis ich auf einem Pfad nur noch eine mögliche Reihenfolge der Eingaben der Eingabe habe. Das ist hier in diesen in diesen Boxen an dem Beispiel notiert. Das hier ist ein Vergleichsbaum. Diese Vergleichsbäume sind fest für eine Eingabegrößig. Ich für jede Eingabegröße habe ich einen anderen.

15:14 Der Punkt ist jetzt auch nicht, dass ein Algorithmus diese irgendwie hinschreibt, sondern für jeden vergleichsbasierten Algorithmus und jedes N existiert so ein Vergleichsbaum. Das ist vielleicht fummelig, den hinzumalen. Mal gucken, ob wir einen ein schönes Beispiel noch bauen können, wo sie das mal machen. Äh, das ist ein bisschen fummelig, aber den gibt es immer, denn der Algorithmus macht die Vergleiche und nur auf Basis der Vergleiche macht er seine Entscheidung. Also muss es den irgendwie geben, wenn er auch ein bisschen im Code versteckt ist.

15:48 Also hierfür für drei Elemente habe ich am Anfang die sechs möglichen Reihenfolgen und unter all diesen sechs gibt es diese drei, die kompatibel sind mit der erste Eintrag ist kleiner als der zweite. Können Sie hier sehen, dass 1 2 3 1 3 2 3 1. Das sind genau die, wo die ersten zwei Elemente schon sortiert sind und die anderen drei waren dann in diesen rechten Zweig. Okay. Äh, dann könnte ich hier einen zweiten Vergleich machen zwischen dem zweiten und dritten Element mitcs 1 2. Wenn die auch schon sortiert sind, dann muss die Eingabe sortiert gewesen sein. So funktioniert das. Das heißt, äh wir haben im allgemeinen eine beliebige Folge von solchen Vergleichen in den Knoten. Die Ausgänge sind immer die zwei Kinder und äh ein Blatt erreiche ich erst, wenn es nur noch eine eindeutig bestimmte Reihenfolge der Eingabe gibt, die genau mit diesen Vergleichen kompatibel ist. Also der Pfad von der Wurzel bis zu einem Blatt gibt mir an, welche Vergleiche da wie ausgegangen sind. Und wenn das eindeutig die Reihenfolge der Eingabe bestimmt, dann darf ich aufhören.

17:08 Okay. Ähm ganz kurz ein paar Fakten über diese Art von Bäumen, über die wir offiziell in der Veranstaltung hier noch nicht geredet haben. Das sind binäre Bäume. Ein binärer Baum ist entweder ein Nullpointer oder so ein externes Blatt. ich mal die hier als diese Quadrate oder es ist ein interner Knoten, die Wurzel von diesem Baum, an der dann wieder zwei binäre Bäume hängen, nämlich ein linkes Kind und ein rechtes Kind. Jeder von denen könnte Nall sein oder wieder eine Wurzel. Das heißt, ich kann mir daraus rekursiv so ein immer größeres Gebilde bauen. Okay. Äh so sieht die so können die z.B. aussehen.

17:48 Äh und unsere Vergleichsbäume hier sind natürlich auch solche binären Bäume. Ähm Notation ist hoffentlich vieles selbsterklärend. Ich will nur auf ein zwei Dinge hinweisen. Ähm, wir werden in der Regel den Knoten irgendwelche Namen geben und nicht einfach nur unidentifizierbare Kreise. Hier sind irgendwelche Zahlen. Ähm, mit der Standbaumanogie erklären sich üblicherweise die Begriffe. Also, dann gibt's einen Vaterknoten und Elternknoten von 11 ist die der Elternknoten 1. Ein hat ein rechtes Kind, die 11. Die Nachfahren von 11 sind z.B. alle diese hier. In der Regel nehmen wir da 11 mit dazu und so weiter und so fort. Ähm, ein Blatt in diesem Sinne würden wir sagen, die Zeh ist ein Blatt, weil das nur Null Knoten Nullpointer als Kinder hat. Äh die die Notation mit dem Null Pointer kommt natürlich daher, dass wir das dann in einem Javaobjekt so repräsentieren, dass es hier einen zwei Einträge gibt für die Pointer zu den linken und rechten Teilbäumen und da kann ein Nullpointer stehen, dann habe ich eben Null und anderer Knoten, wenn es dann noch weitergeht.

19:07 Ähm, die einzige nicht selbsterklärende Notation ist, fangen wir mit den Leveln oder der Tiefe mit 0 oder mit ein anzuzählen. Und ich habe beschlossen, wir fangen mit null anzuzählen. Die Wurzel ist also auf Ebene 0 und dann geht es hier Ebene 1 2 3 bis so weiter. Die letzte Ebene ist die tiefste Ebene, auf der noch so ein echter Knoten ist, also ein nicht. Und dann wäre eben auch die Höhe hier von diesem Baum wäre das maximale Level, also Höhe 5.

19:39 Okay. Ähm den Fakt über binäre Bäume, den Sie dann in den Übungen beweisen werden, den wir hier brauchen, sind diese zwei Dinge. Wenn ich einen solchen binären Baum habe mit n internen Knoten, also n von den Kreisen, dann habe ich genau n + 1 der kleinen Quadrate, der Nullpointer und die Höhe von diesem Baum, egal wie er sonst gebaut ist, ist mindestens Logarithmus von der Anzahl Knoten aufgerundet. können sich überlegen, ähm wesentlichen müssen sich den Worst Case Baum konstruieren, wie viele Knoten kann ich auf die Level unterbringen und dann kann man das relativ leicht zeigen. Ähm bevor wir zum Ende kommen, ganz kurz noch die beiden Dinge zusammenbringen. Dann haben wir nämlich diesen Beweis schon geschafft.

20:30 Also, wir haben für jeden Algorithmus, der vergleichsbasiert ist und für jede Eingabegröße so einen Baum, den Entscheidungsbaum für diesen Algorithmus, die Höhe dieses Baumes entspricht der Worstce Anzahl Vergleiche, denn für jeden für jeden dieser für diesen festen Algorithmus habe ich in den Blättern die ganzen möglichen Reihenfolgen der Eingabe. Und es gibt eine, die mich z.B. hier drei Vergleiche machen lässt und es gibt keine, die mich mehr als drei Vergleiche machen lässt. Also ist hier der Worstcase an Kosten für diesen Algorithmus 3 und das gilt ganz allgemein. Die Höhe von dem Baum ist die Worstcase Anzahlvergleiche. Das ist äh der erste Fakt. Der zweite Fakt ist, wir haben einen binären Baum. Also nach dem äh Theorem, was Sie noch beweisen müssen, wenn der L Blätter hat hier unten, dann ist die Höhe mindestens log.

21:32 Also hier, das sind ähm vielleicht vom Malen her ein bisschen unglücklich, das sind äh nicht die Nullpointerblätter. Ich habe die hier noch als echte Blätter gezählt. Müsste man sozusagen noch, wenn man es zu dem binären Baum aus dem Lämmer machen möchte, noch anhängen. Das heißt, wir wissen was eine Mindestgröße über die Höhe, damit eine Mindestanzahl Vergleiche. Ja, letzter Punkt. Wenn ich einen korrekten Sortieralgorithmus haben möchte, dann muss der für alle möglichen Eingaben reihfolgen, bitte was anderes tun, denn der muss ja mit Vertauschung diese Eingabe zur sortierten Eingabe machen. Es ist nicht möglich, dass die gleiche Folge von Vertauschung zur von zwei verschiedenen Eingaben beides sortiert. Wenn er also korrekt sein muss, muss er nfakultät verschiedene Blätter haben, also Nfakultät verschiedene Pfade zu den möglichen Eingaben. Er kann sich für keine der Eingaben erlauben, die irgendwie mit einer anderen zusammenzupacken. Das gibt uns natürlich unser L mindestens Nfakultät. Müssen wir das nur zusammensetzen. Also, ich habe mindestens l Nakultätblätter. Die Höhe ist mindestens log davon, also ist die Höhe vom Entscheidungsbaum das hier. mindestens log von n Facultät und das ist dann auch die Anzahl Vergleiche im Worst Case. Was dann noch fehlt für diese Asymptotik ist ein bekanntes Resultat, dass Sie vom Cheat ablesen können. Ähm das ist also hier an der Stelle, da man das so häufig gut brauchen kann, ähm ist vielleicht nicht verkehrt, wenn Sie sich das auch ein bisschen einprägen, dass es das auf dem Cheat Sheet gibt. Sie müssen die Formel von mir aus nicht auswendig wissen. Äh dafür haben sie ja das Gheet auch in der Clossware. Aber da kann man dann direkt ablesen. Wenn ich den Logarithmus davon bilde, dann habe ich hier log von diesem ersten Teil gibt mir n* log n - n mal log e. Das ist genau dieser Teil, ja?

23:32 Und der Rest ist sozusagen Kleingemüse. Gut, damit haben wir dieses Theorem bewiesen. Also jeder vergleichsbasierte Algorithmus braucht im Worst Case diese Laufzeit, weil er schon so viele Vergleiche braucht. Sprich Merch und Quicksource sind optimale Sortieralgorithmen. In diesem Sinne be Merch sogar mehr als nur der die Tetaklasse ist ein starkes und Möglichkeitsresultat, was heißt, sie brauchen auf vergleichsbasierten Algorithmen nicht versuchen, das viel zu verbessern, wird nicht hinhauen. Es ist aber auch ein Hinweis auf Auswege. Also ich brauche in der Aussage sowohl Worst Case als auch vergleichsbasiert, um das theorem gültig zu machen. Ähm, wenn ich versuche, den Worstcase wegzulassen, passiert tatsächlich nicht viel. Sie können sich überlegen, dass auch die mittlere Tiefe der Blätter ähnlich ist, aber wenn man das vergleichsbasiert streicht, hat man potenziell Optionen einen besseren Algorithmus zu kriegen. Im Detail besprechen wir das ein effizienter Algorithmen.