Video 7-8: Analyse von Quicksort

0:02 Im nächsten Abschnitt schauen wir uns die Analyse von Quicksort an. Und was es mit diesem zweiten Teil auf sich hat, werden Sie gleich sehen. Bevor wir dahinkommen, noch mal ähm eine kurze Erinnerung, an die wir uns ganz kurz schon angenähert hatten letztes Mal. Scroll, scroll, scroll.

0:32 Wie viele Vergleich Vergleiche braucht Quicksot im Worst Case, wenn ich da n Elemente mit sortieren möchte? hatte Ihnen das passende Bild dazu schon gezeigt, aber ich habe es jetzt nicht noch mal ähm ab den Folien gehabt gerade eben.

1:05 Ich lasse Sie mal kurz schwitzen und dann zeige ich Ihnen das passende Bild und dann können Sie ihre Antwort auch noch mal revidieren. Wenn Sie das Experiment richtig mitmachen möchten, dann müssen Sie jetzt der Versuchung wieder stehen zurückzublättern.

2:18 ein paar mehr Leute als 17, die jetzt bisher abgestimmt haben. Ich kann ja mal wechseln, aber noch sehen sie nicht viel mehr. So langsam scheint sich zu stabilisieren. Jemand gerade aktiv noch am am tippen und dabei am Denken. Äh, lassen Sie mich einmal noch mal auf die passende Folie zurückwechseln. Äh, das ist der Best Case und das war der Worst Case.

3:18 Der Worst Case tritt insbesondere ein, wenn wir in diesem Beispiel, da ist immer rot hervorgehoben, welches Element als Pivot gewählt wurde. Über die Pivotwahl werden wir gleich noch äh reden müssen. Und wenn das aber so ausgeht wie in diesem unglücklichen Beispiel, dass das Pivot z.B. immer das das kleinste ist, das kleinste Element aus der verbliebenen Eingabe, dann passiert das hier. Insbesondere ist hier in Dunkel der Aufwand des Partitionierungsschritts gezeigt, der hier auf diese Ebene abläuft. Das ist natürlich der Extremfall hier. Dieser ähm gute Fall, wo das Pivot die Eingabe schön heftig teilt. Da habe ich hier Aufrufe, die erstmal hier immer kleiner werden. Habe ich hier so ein paar ganz kleine und dann diese hier. Ja, und dann gehe ich auf die rechte Seite und mach da die rechte Hälfte weiter. Und hier sehe ich das überhaupt nicht. Das sieht überhaupt nicht aus wie irgendein Deving Conquer Algorithmus mit zwei rekursiven Aufrufen, sondern ich habe hier so mein äh mein Dreieck gefüllt.

4:23 Gut, dementsprechend ich sehe gerade, ich habe die Folien umsortiert. Ich hatte ihn das noch gar nicht gezeigt, richtig? Sie hatten die Folie dazu noch gar nicht gesehen.

4:52 Dann hätte ich die Frage auch weiter hinten stellen wollen. Ähm, mit dem Dreieck ist die Lösung trotzdem klar. Ich kann ja jetzt die Antwort zeigen. Ähm, also äh hier noch mal was ich in Ich meine, wir wir sind nicht so schnell gewesen. Letztes Mal habe ich es verschoben. Hahaha. Gut. Also, das Bild, die Art von Bild kennen Sie schon. Ähm, hier eben wie eben erklärt, sieht man immer den Partitionierungsschritt, wo das Pivot landet und dann die rekursiven Aufrufe. Ein typischer Fall ist etwa so wie das hier ausgeht und auch schon das dieses erste dieses erste Paper gedruckt 62 wie immer indem Tony H diesen Algorithmus das erste Mal vorgestellt hat, enthält eine kleine Tabelle in der er Laufzeitexperimente gemacht hat auf der Maschine von der Firma, für die er damals gearbeitet hat als als Entwickler äh mit riesigen Eingang Aen und sie sehen Quicksord war da schneller als Merchsort und die letzten beiden Zahlen hier waren schon Hochrechnung, weil die Maschine gar nicht genug Arbeitsspeicher hatte dafür.

6:19 Ja, wenn man das wiederholt auf heutigen Rechnern mit üblicheren Eingabegrößen, wie man sie wie man sie heute braucht, dann sieht man auch ein einen deutlichen spürbaren Unterschied zwischen Quicksot und Merchsort. Quicksot ist deutlich schneller. Ähm, aber es ist auch keine gigantische Größenordnung dazwischen.

6:37 Und na gut, auf einem Rechner, der tatsächlich so viele Vergleiche pro Sekunde macht, ist selbst eine Billion sortieren äh keine messbare Zeit vergangen. Die Folie mit dem ersten Teil Merch hatten wir schon äh mit der gleichen mit der gleichen Conclusion, dass eben bessere Algorithmen deutlich mehr ausmachen können als die bessere Hardware, wenn die Eingaben nur über genügend Größenordnung hinweg verbessert werden.

7:14 Die Folie ähm habe ich so ein bisschen jetzt vorweggenommen, aber lassen Sie mich trotzdem noch die Animation dazu zeigen. Worauf Sie achten möchten, ist wie sehr sich die Laufzeit unterscheidet zwischen diesen verschiedenen Eingaben.

7:36 Vielleicht ein bisschen langsamer. Also in in allen Fällen läuft der Quicksot Algorithmus, wie er auf den Folien ist, mit ähm einer kleinen Modifikation, was die Pivotowahl angeht.

8:01 Sind wir dann fast fertig. Sehen um und bei werden die gleich schnell fertig. Sieht also aus ähm als wäre Quicksort gar nicht so arg Datenabhängig.

8:18 Hat sich natürlich jetzt wesentlich nur die zufälligen Eingaben geändert. Auch hier wieder fast gleichzeitig fertig, aber nicht ganz. Sieht man wahrscheinlich. Okay, der Schein mit dieser Datenunabhängigkeit, der trügt und der Grund ist, dass ich hier schon was eingebaut habe, auf das wir zurückkommen werden. Da sind zufällige Pivots gewählt und dann kann man das halbwegs erzwingen.

8:50 Ähm, BestCase ist dieser Fall, wenn das Pivot immer genau in der Mitte liegt und ich schön die Eingabe halbieren kann, dann habe ich tatsächlich hier ähm werden wir nicht im Detail analysieren, weil wir uns noch was anderes angucken wollen als sortieren am Ende vom Tag. Wenn sie aber aufmalen, also quasi dieses Bild zusammenschieben, dann passt diese Eingabe mit dieser Eingabe die zwei zusammen, ergeben das zweite Level von so einem rekursiven Aufruf. Ich habe hier den obersten Partitionierungsschritt, der kostet mich etwa n Vergleiche. Dann habe ich zwei Partitionierungsschritte auf dem Level drunter. Die kosten mich jeweils n halbe, aber ich habe zwei davon. Das heißt, ich hätte hier zweimal x n halbe. Wenn ich immer perfekt in der Mitte teile, dann habe ich hier und diesen noch kleineren vier Stück. Die sind schon ein bisschen kleiner, da fehlen jeweils die Pivots aus dem Level oben drüber, aber es sind höchstens so viele, wie ich die Elemente vorher hatte. Also, wenn ich hier ähm das Bild dann irgendwann mit echten Eingabegrößen male und nicht einfach nur so kontinuierliche Balken, dann würde ich hier ja jeweils ein Element das Pivot schon verloren haben.

10:20 Dementsprechend hier auch und hier auch. Die sind schon nicht mehr Teil der Eingabe, aber wir sind mal großzügig und zählen die noch mal mit. Dann habe ich hier höchstens 4 x n viel und das mache ich so lange, bis ich am un angekommen bin bei einzelnen Elementen. Und wie wie oft muss ich eine Eingabe halbieren, bis wir bei einzelnen Elementen angekommen sind? Das hatten wir beim Merchort genauso. Also irgendwann habe ich nur noch einzelne Elemente.

10:54 Da habe ich auch noch mal höchstens Kosten n. Bei einzelnen Elementen habe ich eigentlich schon keine Kosten mehr. Ich könnte ein Level oben drüber aufhören, aber ich muss das etwa log n mal halbieren. Das ist genau die gleiche Analysee, die wir bei Merchsort hatten. Deswegen hier nur noch mal in der informellen Version.

11:16 Das ist der Best Case von Quicksord. Der ist genau nach dem Muster von Merchsort. Wenn wir den immer hätten, wären wir zufrieden. Leider ist das nicht der Fall, wenn der äh wie in der Frage, wenn das wenn das Quick, wenn das Pivot immer eins der Extremelemente ist, kleinstes oder größtes, dann sehen Sie optisch es ist so ein Dreieck und das hatten wir jetzt wieder in den primitiven Sortieralgorithmen schon mehrfach analysiert. Das sind immer n quadrat halbe asymptotisch.

11:46 Wenn ich wenn ich mir das diskrete wegdenke, ist es das kann ich das Dreieck verdoppeln zu einem Quadrat, dann habe ich mein n Quadrat. Also was nun? Ähm es kann ganz gut ausgehen und es kann ganz schlecht ausgehen. Aus den empirischen Daten scheint zu folgen, dass es meistens gut geht. Aber das ist keine sehr befriedigende Antwort, wenn wir wissen wollen, ob wir jetzt diesen Quicksot Algorithmus verwenden können.

12:13 Das habe ich mal das Quicksort Puzzle genannt. Üblicherweise ist Quicksort der schnellste allgemeine General Purpose Sortieralgorithmus. Das ist was man immer wieder beobachtet, wenn man die wenn man verschiedene vergleicht. Das werden Sie den Übungen mal noch zum zum mal als als Eigenversuch machen. Das hat wahrscheinlich hauptsächlich damit zu tun, dass die innersten Schleifen, also der Teil des Codes, der am häufigsten ausgeführt wird, bei Quicksort sehr klein ist. Sind nur sehr wenige Befehle, die den Hauptteil ausmachen. Außerdem braucht er keinen Zusatzspeicher, das hat andere Vorteile, aber ist natürlich auch für Cashing und so weiter hilfreich. Und ich lese sequenziell über die Eingabe. Das macht zwar Merchsort auch, aber Quicksot liest ein bisschen weniger. Äh insbesondere dieser Punkt. Ja, bei Merchsort, selbst wenn ich clever bin und dieses Pingpong Spiel mache, lese ich einmal hier und schreibe einmal hier. Äh Quicksot kommt da mit weniger elementaren Operationen aus.

13:08 Trotzdem habe ich diesen Worst Case. Wie kann das denn nicht ein Problem sein? Um der Frage auf den Grund zu gehen, schauen wir uns den Average Case für Quicksort an. Also angenommen, die Eingabe ist eine zufällig gewählte Reihenfolge der Elemente, die wir sortieren. Was ist denn dann die was sind dann die Kosten von Quicksort? Das Modell, das dass wir da zugrunde legen, das kennen Sie schon. Damit hatten wir schon damals ähm den äh Insertion Sort und so weiter analysiert, die Bubble Sort, Insertion Sort, die primitiven Sortieralgorithmen. Also alle möglichen Reihenfolgen von n- Elementen sind gleich wahrscheinlich, da wir vergleichsbasiert sind. Also die Algorithmen immer nur vergleichen zwischen zwei Lemen, welches ist kleiner, welches ist größer. Ist egal, was das für Objekte sind. Da können wir es uns bequem machen und da einfach die ersten n inte Integer für verwenden. Dann gibt's genau diese n Fakultät vielen verschiedenen Reihenfolgen. Und sozusagen was hier als Annahme dahinter steckt wieder erstmal ist, dass die alle verschieden sind Das werden wir erstmal einfach so stehen lassen. macht das Rechnen einfacher.

14:36 Also, das Modell kennen Sie schon, das hatten wir damals auch schon verwendet und festgestellt, die Anzahl Inversionen ist quadratisch. Das heißt, jedes primitive Verfahren, was immer nur eine Inversion pro Swap los wird, äh ist hoffnungslos ähm in diesem quadratischen Average Case gefangen. Quicksot macht das natürlich besser, wenn die wenn Sie sich überlegen, was für Swaps wir in Quicksot haben, diese lange Distanz.

14:59 Beim Partitionieren haben wir eventuell einen einen Swap von hier nach da. Der könnte eine lineare Anzahl Inversionen loswerden. Das heißt, potenziell geht das viel schneller oder es ist zumindest keine Hürde von der Anzahl ähm Inversoren hier. Äh was hier jetzt für uns wichtig ist, wir hatten in unserem Algorithmus noch nicht so genau festgelegt, wie wir das Pivot wählen. Ähm für zufällige Permutation ist es auch nicht so wichtig. Sagen wir mal, wir nehmen das erste. Also, es ist nur als Gedankenspiel, wenn Sie mögen, dass wir immer dieses AL als Pivot wählen.

15:44 Da das alles symmetrisch und zufällig ist, hätte ich auch jede andere feste Position nehmen können. Es macht keinen Unterschied. dann ist dieses Pivot eine zufällig gewählte Zahl zwischen 1 und n in so einer zufälligen Permutation.

16:02 Dementsprechend hat jeder Wert auch die Wahrscheinlichkeit 1 ge n. Das ist die die Haupteigenschaft, die wir ausnutzen wollen. Das heißt, wenn Sie sich anschauen, was unser Partitionierungsschritt macht, der bringt ja am Ende diesen Wert P an die endgültige Position, wo er im in der sortierten Folge stehen muss. Wenn ich die Zahlen 1 bis n sortiere, dann ist es natürlich auch genau an der Position p - 1, weil wir bei 0 anfangen.

16:35 Wie groß sind dann die beiden rekursiven Teilprobleme, auf denen ich noch weitermachen muss? Der Teil hier ist p - 1 groß Wenn ich also p etwa in der Mitte habe, dann sind sie beide n halbe groß. Aber es kann natürlich auch alles andere vorkommen. Der wichtige Teil ist, dass ähm dass das uniform gewählt ist. Ich habe also die gleiche Wahrscheinlichkeit für jede Position als äh Split BE zwischen den zwei rekursiven Aufrufen. Okay, was wir damit tun können, ist eine Rekursionsgleichung aufstellen, wie wir es auch für Merchsort und andere Algorithmen schon getan haben. Die ist aber ein bisschen bisschen weniger freundlich. werden sie gleich sehen. Erstmal als Notation C von N sei jetzt die die durchschnittliche, also erwartet über zufällige Eingaben. Ich hätte hier auch sagen können, die mittlere Anzahl vergleiche, wenn ich eben ähm alle diese Eingaben äh betrachte. Die erwartete Anzahl Vergleiche, wenn wir zufällige Permutationen sortieren und nach dem Bild von eben setzt sich das zusammen aus den Kosten, die ich für einen Partitionierungsschritt habe. Die habe ich immer und dann habe ich rekursive Kosten für die Teilprobleme.

18:04 Okay, das kann man so aufschreiben. Für eine Eingabe der Länge 0 muss ich nichts mehr tun. Für eine Eingabe der Länge 1 muss ich auch nichts mehr tun. Aber für den üblichen Fall, dass ich mindestens zwei Elemente habe, äh muss ich mir anschauen, was kostet ein Partitionierungsschritt. Da muss man jetzt präzise zählen da. Das ist für genau unseren Code. Also für das Horetric Schema mit diesen mit den Zeigern, die aufeinander zu laufen.

18:41 NCS. Ähm, das kann so um plus- 1 variieren, je nachdem, was sie machen. Eigentlich ist n + 1 ein bisschen zu viel, wenn sie sich überlegen, wollen ja eigentlich jedes Element mit dem Pivot vergleichen. Warum macht der Algorithmus da ein zwei mehr? Weil er eventuell über ein Rand rausläuft und so ein Sentinel Trick verwendet und weil eventuell die Point das sich einmal kreuzen, bevor wir es merken. Das ist aber sozusagen darauf kommt's nicht so sehr an. Der wichtige Teil ist, dass hier etwa ein N steht. Und dann habe ich die rekursiven Aufrufe. Jetzt ist das Ganze ein Erwartungswert. Das heißt, auch für die rekursiven Aufrufe muss ich über alle Möglichkeiten mitteln. Insbesondere sind die Möglichkeiten, welches Pivot ich bekommen habe. Davon hängt ja ab, wie groß die Eingaben sind. Das heißt, ich habe dieses dieses P, das hätte ich vielleicht als großes P nehmen sollen. Das ist nämlich eine Zufallsvariable. Aber verlassen wir es hier mal bei dem Wert klein p. Also, ich halte ähm alle ich gehe über alle Möglichkeiten, die dieses dieses Pivot als Wert haben kann.

19:46 Jeder hat Wahrscheinlichkeit 1 durch n und dann habe ich diese beiden Größen für den re für die beiden rekursiven Aufrufe. Was ich nicht auf die Folie gepackt habe, was man eigentlich auch noch hier argumentieren muss, ist, dass überhaupt eine sinnvolle Rekursion ist, denn diese zwei rekursiven Aufrufe sind ja nur dann wieder ein C von irgendwas, wenn ich die auf einem auf einer zufälligen Permutation ausführe. Das kann man jetzt bei Quicksot argumentieren, dass das tatsächlich der Fall ist. Also selbst wenn wir hier partitionieren, ist die Eingabe, die wir erzeugen, immer noch so zufällig wie vorher. Intuitiv können Sie argumentieren, ich habe nichts gelernt über z.B. die Elemente im linken Aufruf, weil ich die nie verglichen habe. Ich habe immer nur Elemente mit Pivot verglichen. Von zwei Elementen, die kleiner sind, weiß ich vorher wie nachher nicht in welcher Reihenfolge sie sind. Also kann ich da sozusagen auch gar nichts kaputt gemacht haben. Ich habe gar kein Wissen erlangt, dass mir das irgendwie erlaubt hätte.

20:50 Also, das ist die Frage nach Randomness Preservation. Äh können Sie für die Vorlesung hier ignorieren? Ich habe es nur erwähnt, weil ja doch auch einige Mathematiker die Vorlesung hören. Falls sie sich wundern, warum das überhaupt eine gültige Rekursion ist, ähm dann kann man das nachprüfen. Sie können das aber erstmal einfach als als Fakt hinnehmen. Werden wir in der Vorlesung nicht weiter drauf aufbauen. Selbst wenn wir die Rekursion hier gegeben haben, sieht die nicht aus, als würde die in das Master Theorie im Schema passen, denn die hat ja hier eine Summe über alle kleineren Parameter für dieses p. Das p läuft von 1 bis n. Damit ist das hier von 0 bis n - 1 und das hier äh die gleiche Summe rückwärts. Das sieht nicht nach einer Rekursion aus, die man überhaupt präzise lösen kann. Im gibt auch Beispiele, wenn man da ein bisschen mit spielt, kriegt man Rekursion, für die man keine schöne geschlossene Form kennt. In dem Fall ist es nicht so. Man kann die exakt lösen, wenn man diese harmonischen Zahlen benutzt.

21:58 Ähm, ich habe bisschen hin und her überlegt, das ist eine ganz schöne Analyse, die auch Spaß macht, aber ich habe dann doch beschlossen, ich belasse die in effiziente Algorithmen. Das ist ein bisschen äh clevere Rechentricks und Summen bilden. Stattdessen möchte ich Ihnen eine Analyse zeigen, die weniger mathematisch ist, sich besser verallgemeinert auf andere Verfahren und vielleicht ein bisschen eher ähm den algorithmischen Hintergrund zeigt, warum Quicksort doch meistens gut geht. Dafür, was wir nicht rausbekommen, ist so eine präzise Lösung. Hier können Sie genau rausbekommen, äh was ist was ist die exakte Anzahl Vergleiche in diesem Erwartungswert. Das kriegen wir mit meiner einfacheren Analyse nicht hin. Da kriegen wir nur eine Thetak Klasse. Aber da hat man uns beim Master Theorem ja auch mit begnügt. Also, wir machen einen Trick, den man tatsächlich öfter anwenden kann, wenn man Algorithmen analysieren möchte, die irgendwie schwierig präzise zu analysieren sind. Wir machen das einfach nicht, sondern wir analysieren einen anderen Algorithmus, einen, der leichter zu analysieren ist, der aber höchstens mehr Kosten verursacht als der ursprüngliche. Das ist der Trick dabei. Wir designen einen Algorithmus, der sich an paar Stellen explizit dümmer verhält, als er könnte, aber das macht eben die Analyse dann leichter. Dann kriegen wir eine obere Schranke für die Kosten. Ist oft gut genug, werden wir sehen. Äh, in diesem Fall ist es der Tobsuchtanfall Quicksort.

23:30 Ähm, ist natürlich kein kein wirklich sinnvoller Algorithmus. Trotzdem habe ich ihn mal als Code beschrieben, um zu zeigen, wie er präzise funktionieren würde, aber ich möchte ihn den nicht vorschlagen als einen echten Sortieralgorithmus, auch wenn er funktioniert. Der macht einfach folgendes. Er fängt an wie Quicksort auch, hat aber hier noch eine Wild Schleife. Dann partitionieren wir mal mit einem Versuch. Und wenn aber das P, das wir zurückbekommen, zu weit links oder zu weit rechts ist. Also, wenn ich ähm im linken, wenn ich im mittleren, in der mittleren Hälfte bin, ich sollte vielleicht einfach das Bild dazu malen. Also hier ist unser A von L bis R, den Bereich, den wir noch sortieren. Ich hätte gerne, dass mein Pivot hier genau in der Mitte ist, aber da kann ich lang warten. Das könnte ja passiert nur mit Wahrscheinlichkeit 1 durch n. Wir sind also ein bisschen weniger streng. Wir sind zufrieden, wenn das Pivot irgendwo hier in dieser mittleren Hälfte liegt.

24:31 Dann machen wir das Break und machen rekursiv weiter wie gehabt. Aber falls nicht, sind wir ganz ärgerlich und äh dass dieses Pivot so doof ist und schmeißen alles über den Haufen. Was das hier heißt ist, wir wir würfeln die Eingabe durcheinander und erzeugen uns eine neue zufällige Permutation von diesen Elementen.

24:52 Das ist deshalb definitiv teurer als der normale Quicksort, denn selbst wenn ich nach diesem ein Partitionierungsschritt das schlechtest mögliche Pivot habe, habe ich ja trotzdem ein Element für den rekursiven Aufruf ausgeschlossen. Einfach das alles zu verwen und ja trotzdem die Kosten für die Palationinierung gehabt zu haben ist nie besser. Aber es macht die Analyse einfacher, wie wir es sehen werden. Wir werden hier beweisen, dass diese ähm der der Tobsoft Quicksort die erwartete Anzahl T von N für den, die ist einerseits eine obere Schranke für das C, den echten Quicksort und ist aber auch in groß O von N log n, also weit weg von unserem N² halbe Worst Case.

25:42 Und na ja, das folgt natürlich direkt daraus, dass auch das C in Großfen n log n ist. Deswegen hier noch mal als Kolorar Corollar aufgeschrieben, dass der Average Case für Quicksort auch groß von Nlogin ist. Die spannendere Frage wird die Analyse sein. Also versuchen wir diesen Tobs of Quicksort zu analysieren.

26:31 ist die Wahrscheinlichkeit für einen Tobsuchtanfall zu berechnen in einer so einer Iteration. Das passiert ja genau dann, wenn unser P nicht in dieser mittleren Hälfte liegt.

26:55 Also noch mal das Bild dazu. Ich teil mein Array in Viertel und wann immer ich in der mittleren Hälfte lande, dann bin ich zufrieden und ansonsten hat Quicksot seinen Ausraster.

27:19 Ich habe also n halbe Position. Wir ignorieren mal das Runden bzw. nehmen an, das ist eine zweier Potenz. Ähm, könnte man eine obere Schranke machen, dann ist äh macht's die Rechnung bisschen bisschen nerviger. Ignorieren wir hier mal, dass wir eventuell nicht gerade aufgehen.

27:50 Also, wir haben halbe Pivots, die gut ausgehen und halbe, die schlecht ausgehen. Ich habe insgesamt jedes Pivot mit Wahrscheinlichkeit 1 durch N. Also Wahrscheinlichkeit einhalb, dass ich zufrieden bin und einhalb, dass ich ausraste.

28:23 Wenn Sie mögen, können Sie es hier so wählen, dass das durch die Rundung dann höchstens das ist. Ist natürlich ein halb. Der zweite Schritt ist, die erwarteten Kosten zu bestimmen, bevor wir einen rekursiven Aufruf machen.

29:02 Wenn Sie sich den Code anschauen, was was dafür wichtig ist, ist wie oft wir diese Schleife durchlaufen. Jeder Aufruf hier innen steht ja hier noch mal macht n + 1 Vergleiche und wir machen diesen Durchlauf so oft wie wir eben nicht rausspringen. Also ich mach's immer mindestens einmal. Höchstens kann ich nach dem ersten Partitionieren rausspringen, aber ich könnte da auch eine Weile festhängen. Ähm das unangenehme an diesem Algorithmus ist tatsächlich, der Mark nie terminieren. Die die Worstcase Laufzeit ist unendlich, denn ich könnte immer Pech haben und auf ewig schlechte Pivots ziehen.

29:39 Für die erwartete Laufzeit gilt es nicht, wenn wir auch gleich beweisen. Ähm grundsätzlich sind solche Algorithmen vielleicht ein bisschen, da hat man so ein bisschen ein ungutes Gefühl. Ähm Antwort 1 ist natürlich, das ist kein echter Algorithmus, den wir verwenden wollen, sondern ja nur ein Analysevehikel. Aber Antwort 2 ähm sie verwenden oft regelmäßig Algorithmen, die genau das tun, potenziell nie terminieren und es geht halt gut, weil sie mit Wahrscheinlichkeit beliebig groß nach bester Zeit fertig sind. ähm ist also kein fundamentales Hindernis, um solche Algorithmen einzusetzen. Klassisches Beispiel dafür ist Rejection Sampling. Aber das nur so am Rande.

30:35 Der Parameter, der uns interessiert, ist die Anzahl Durchläufe der Weilschleife. Dann sind nämlich die Gesamtkosten. Ähm, der sollten wir ein Namen geben. Dann sind die Gesamtkosten für diese, kann ich vielleicht da oben hinschreiben, ist dann x. Ähm, lassen Sie uns mal die Notation so verwenden, dass der Erwartungswert von x mal n + 1 vergleiche.

31:07 Also müssen wir nur den Erwartungswert der Anzahl Schleifendurchläufe bestimmen. Und was wir über die Schleifendurchläufe wissen, ist, dass wir nach jedem Durchlauf mit Wahrscheinlichkeit ein halb noch einen machen.

31:27 Also, was sich schön ausdrücken lässt, ist, dass die Wahrscheinlichkeit, wir können vielleicht mal ein paar Werte aufschreiben, also die Wahrscheinlichkeit, dass x1 ist, ist ein/H/B. Dann hätte ich einen Durchlauf gemacht und danach direkt Glück gehabt. Wahrscheinlichkeit, dass x2 ist, ist, na ja, ich habe im ersten Durchgang Pech gehabt, aber im zweiten Durchgang hatte ich dann Glück, also ein Viertel. Und äh vielleicht erkennen Sie auch das Muster bzw. Also die geometrische Verteilung für diejenigen, die das kennen.

32:00 Damit ich drei Durchläufe brauche, muss ich zweimal Pech gehabt haben und dann einmal Glück. Okay, also allgemein die Wahrscheinlichkeit, dass mein X größer gleich k, die ist genau 2- K.

32:24 Passt auch auf unser Schema. Und dankenswerterweise summiert sich das auch, wenn ich über alle Werte äh alle natürlichen Zahlen ab eins summiere zu eins, was ja eine Wahrscheinlichkeitsverteilung auch tunlichst machen sollte. Äh jetzt müssen wir noch ausrechnen, äh Moment mal, was habe ich hier getan? Das hier ist ein ist gleich.

33:30 Also, wir können wir können hier in dem Fall auch direkt die Summe so verwenden, äh da sie in den Übungen diese Summe gelöst haben.

33:39 Das ist einfach die Definition vom Erwartungswert. Wenn wir einsetzen, was wir jetzt über die Wahrscheinlichkeit gelernt haben, dann ist es einfach das hier und dann können Sie sich die Ableitung der geometrischen Reihe verwenden oder auf dem Treathe nachschauen.

34:07 Vielleicht hät ich das hier wieder als einhalb schreiben wollen, sonst passt es genauer zu dieser Form. Das heißt, der ähm Erwartungswert davon ist ist 2. Die geometrische Reihe hat man in der Regel ab null summiert. Dann äh soll wir das noch mal präzise nachrechnen, ob das stimmt?

34:42 Wenn man sich nicht unsicher ist, kennen ja das Spiel. Was wir brauchen ist diese hier. Bei uns läuft die Summe ab 1, nicht ab null. Das heißt, ich muss äh den Term hier wieder abziehen. Also unser C ist ein/H/B.

35:17 Komm schon. Ein/b geil durch 1- 1/ quadrat. Aber wir ziehen den Term für i = 0 wieder ab. Der ist aber einfach null, nicht? Der passiert gar nichts. Okay, das hier ist ein/HB Quadrat ist ein Viertel und kürz wieder raus.

35:58 das heißt also um und bei sind die Kosten für eine ein Partitionierungsschritt inklusive aller Tobsuchtanfälle in Erwartung nur 2n als asymptotische Approximation. Ja. K ist hier eine gebundene Variable, die können Sie nicht aber vor die Summe ziehen oder habe ich es falsch verstanden?

36:45 Nee, K ist hier schon ähm ist der Sumindex, aber also sie können natürlich ähm gibt gibt verschiedene Wege die Summuts die Reihe auszurechnen. Ja, wir sind aber immer noch nicht fertig, denn jetzt wissen wir zwar, dass in Summe diese Wildschleife in aller Regeln nur 2n + 1 2n + 2 Vergleiche kostet in Erwartung.

37:16 haben wir immer noch diese seltsame Rekursion und an der Stelle kommt jetzt zum Tragen, dass wir diesen Tobsuchtquort verwenden, der da die Rechnung einfacher macht.

37:35 Damit können wir die Rekursion leichter abschätzen. Was nämlich passiert ist, dass wenn ich kein Tobsanfall bekommen habe, mein Pivot ja immer in der in der mittleren Hälfte liegt. Also im schlimmsten Fall und Worst Case ist jetzt bezogen nicht auf die Kosten für das Palzin sonden, wo das Pivot für die Rekursion landen kann.

38:20 Dann habe ich es immer z.B. bei ein Viertel. Also versuch es mal ein bisschen sauber zu malen. Hier wäre mein Pivot im schlechtesten Fall. Dann habe ich die beiden rekursiven Aufrufe hier links davon und hier rechts davon.

38:38 Auf diesem Level habe ich auch wieder hier etwa 2n Kosten für den ersten Partinierungsschritt inklusive Wutanfälle. Hier habe ich 3/4 N und noch ein Nweils mal 2. In Summe ist es auch wieder 2n Wut vergleiche inklusive Wutanfälle.

38:58 Jetzt mache ich hier natürlich rekursiv weiter. Ich zerteile hier wieder immer an der Worst Case Position. Das heißt, ich habe so eine Rekursion, wo immer die rechte Seite deutlich größer ist als die linke.

39:15 Sprich, die passt auch immer noch nicht so wirklich auf das Master Theorie. Muss sie aber nicht. Wir können die Rekursionsbaummethode manuell anwenden. Das ist, was ich hier Ihnen versuche zu zeigen. Ähm, ich mach's mal zu kleiner G = 2n, weil wir immer wieder die Pivos hier ja verlieren, aber wir sind ja sowieso nur an der oberen Schranke interessiert. Das heißt, ich kann das hier soweit fortsetzen, bis ich irgendwann hier einzelne Elemente habe. Da bin ich dann z.B. schon fertig. Hier müsste ich noch weitermachen und hier müsste ich noch weitermachen und so weiter und so fort. Wie lange kann dieses Spiel weitergehen?

39:52 für diesen Worstce Case, den wir uns anschauen, so lange bis der größere der beiden Teilprobleme auch nur ein Element enthält. Also, wenn ich das hier weiterführe, irgendwann ist auch dieser rechtere Aufruf nur ein Element.

40:07 Wie lange muss ich das machen? Wie oft muss ich den ungleichen äh die ungleiche Aufteilung hier machen, bis ich bei einem Element bin? Na ja, nicht mehr Logarithmus zur Basis 2 von n, sondern Logarithmus zur Basis 4 von n, weil meine Eingabe immer um noch mal etwas sauberer. Meine Eingabe nach i Schritten hat immer noch 3/4 hoch i mal n Elemente und ich hätte gerne, dass das nur noch ein Element ist. Die diese Ungleichung wollen wir nach I auflösen.

40:48 Ja, dann ähm teilen wir durch n und wir bilden den Kehrwert. Dann dreht sich das ähm Gleichheitszeichen um. Da geblieben, verschieb es mal ein bisschen, dass ich vielleicht nicht so leicht hier auf die gefährliche Stelle komme.

41:42 Also, ich habe eine andere Basis im Logarithmus, sprich einen schlechteren konstanten Faktor vorne dran, aber es ist trotzdem insbesondere groß von N. Ich habe also einen einen Rekursionsbaum der Höhe log zu Basis 4/ Dr von n höchstens und auf jeder Ebene habe ich höchstens 2n Vergleiche. Das ist eine großzügige Schätzung, weil ja weit hier unten dieser ganze linke Teil schon leer sein wird, aber obere Schranke ist es trotzdem. Das heißt, die Gesamtkosten für unser T von n ist höchstens diese Höhe log 4/3 von n mal 2n und das ist groß Ohr von n log n und das ist die Behauptung gewesen. Den anderen Teil, das Quicksord höchstens weniger braucht, hat ich am Anfang schon argumentiert, ein Tobsuchtanfall kriegen und alles durcheinander würfeln und trotzdem dafür zahlen hilft nie. Dementsprechend hat Quicksot höchstens diese Kosten.

43:00 Äh lassen Sie mich, bevor wir weitermachen, noch erwähnen, dass man diese Art von Analyse oft auf andere äh Algorithmen auch anwenden kann. ähm diese Idee, dass man eine Rekursion hat, die von was zufälligem abhängt, die wird uns auch in anderen Algorithmen begegnen. Vielleicht nicht in diesem Modul, aber in fort fortgeschrittenen ähm Algorithmen, passiert das ab und an und dann ist es ein Standardtrick zu sagen, ich hoffe mal nicht nur drauf, dass es nach einem Schritt klappt, sondern ich gebe mir eine zufällige Anzahl Schritte. Wenn ich zeigen kann, dass es nicht viele sind in Erwartung, dann habe ich trotzdem gute erwartete Gesamtkosten und kann dann mit dieser stärkeren Garantie, wie hier das Pivot ist in der mittleren Hälfte die Analyse vereinfachen.

43:49 Was wir daraus lernen ist, dass Quicksort eben für zufällige Eingaben ähm sehr viel näher an diesem Best Case ist und sehr weit weg von seinem Worst Case ist. Man kann da noch mehr mathematisch zu zeigen, wie unwahrscheinlich tatsächlich dieser quadratische Fall ist. Äh darauf will ich nicht weiter eingehen. Äh worum es mir hier geht, ist wenn die Eingabe zufällig ist, ist Quicksort fast so gut wie im Bestase. Darauf kann man sich gut verlassen. Leider gilt diese Annahme aber nur, wenn mal wenn der erste Teil von dem wenn auch auch stimmt, wenn die Eingabe zufällig ist. Und das ist so ein bisschen gefährlich, sich darauf zu verlassen, je nachdem, wie man so ähm ein eingestellt über die Welt ist. Äh spätestens, wenn es darum geht, dass man irgendwie Cyburity Attacken äh zu erwarten hat, könnte ja jemand auf die Idee kommen, ihren Webserver gezielt äh damit zu beschäftigen, Listen zu sortieren, die Quicksot den Worst Case treiben. Ist auch kein hypothetisches Szenario.

44:50 Also will man sich darauf eigentlich nicht verlassen, aber Quicksort ist doch so ein toller Algorithmus, können wir den nicht trotzdem irgendwie retten? Der war ja deutlich schneller als Merchsort. Und der Punkt dafür ist, äh, wenn wir wie bisher in der Analyse auch eine feste Position für das Pivot wählen, dann müssen wir darauf hoffen, dass die Eingabe zufällig ist. Aber wir können auch stattdessen ein zufälliges Pivot wählen, also irgendeins der Elemente aus dem Bereich, die den wir sortieren. Und wenn Sie sich anschauen, was wir gerade in der Analyse verwendet haben, dann war das präzise, dass jede jeder Wert des Pivots mit Wahrscheinlichkeit 1 dur n gewählt wird. Das haben wir hier jetzt einfach erzwungen, unabhängig von der Eingabe. Völlig egal, wie die Eingabe sortiert ist. In Initial wähle ich hier jedes Pivot mit gleicher Wahrscheinlichkeit, indem ich einfach zufällige ähm zufällige Bits bestimme, bis es dann so ist. Und damit weiß auch niemand, wer äh was das nächste Pivot ist, auch kein Angreifer. Ich weiß es ja selbst nicht.

45:58 Das ist manchmal ähm auch außerhalb der Algorithmik ein beliebtes Szenario beliebte Strategie. äh die hier aber insbesondere bewirkt, dass es gar keinen Worst Case in dem klassischen Sinne mehr gibt, denn ich mache einfach für die gleiche Eingabe immer wieder andere Dinge und ich weiß, wenn ich die Eingabe gut genug durchgemischt habe, dann bin ich in meinem guten Average Case. Das heißt, das funktioniert auch mit hoher Wahrscheinlichkeit ähm mit geringen Kosten.

46:32 Die genau gleiche Analyse bleibt also gültig äh mit so einem kleinen äh Edgecase, den wir aber jetzt ähm hier nicht weiter anschauen. Äh was ich noch mal kurz gegenüberstellen möchte, sind diese zwei unterschiedlichen Dinge Zufall oder zufällige Dinge einzusetzen.

46:48 Auf der einen Seite Average Case Analyse, was wir eben gemacht hatten und auf der anderen Seite ein randomisierter Algorithmus, der gezielte zufällige Entscheidung in den Algorithmus einbaut.

47:00 Also in der einen Welt ist der Algorithmus deterministisch. Wir wählen immer die gleiche Position als Pivot, aber wir nehmen an, die ähm die Eingabe ist zufällig, aber für die gleiche Eingabe kriegen wir die gleiche Berechnung, während ein randomisierter Algorithmus nicht deterministisch ist. Der macht immer wieder andere Dinge, eben abhängig von diesen Zufallspits, die er sich zieht. Äh für Average Case Analyse nehmen wir an, die Eingabe hat eine bestimmte Verteilung, während für randomisierte Algorithmen können wir mit dem schlimmsten mit der schlimmsten Eingabe leben und sorgen dafür ähm, dass es einem Gegner trotzdem nicht viel hilft. In beiden Fällen sind die Kosten erwartungswerte, aber einmal ist die Erwartung oder dies das zufällige die Eingabe und im anderen sind die zufälligen Bits, die wir unter Kontrolle haben als Algorithmusdesigner. Deswegen ist das Rechte, eine deutlich robustere Art Zufall zu verwenden. Die Analysetechniken zeigen das nicht. Oft ist die Rechnung, die man macht, um diese Kosten zu bestimmen, identisch, weil wir in beiden Fällen einen Erwartungswert bestimmen. Aber für die algorithmische Anwendung ist es eben viel viel robuster, diese Randomisierung, den Zufall selbst in die Hand zu nehmen und zu erzwingen, dass wir den Average Case haben. Das ist ein ein Trick, den man nicht nur bei Quicksort einsetzen kann, deswegen habe ich das hier noch mal ein bisschen rauskehren wollen. Es ist insbesondere bei Quicksort besonders hilfreich, weil da der Unterschied zwischen Best und Worst Case so gravierend ist. und der Average Case sehr nah am best case liegt.

48:35 Wie bei Merchsort gibt's so ein paar Tricks, die man auch bei Quicksot zum Einsatz bringen kann, um die Laufzeit in der Praxis noch ein bisschen zu verbessern. Gleicher Trick wie bei Merchsort. Für kleine Teilprobleme lohnt es sich einen schnelleren Algorithmus zu nehmen, statt diesen rekursiven, einfach weil ich sehr viele Teilprobleme mit kleinen Eingaben habe und der rekursive Aufruf und all das so ein bisschen overhead kostet, den z.B. Insertion Sort vermeiden kann.

49:04 Der wichtige zweite Teil ist eine gute Wahl der Pivots. Eine zufällige ähm Wahl ist schon robust in dem Sinne, dass sie so gut ist wie der Average Case. Äh man kann aber tatsächlich noch noch ein bisschen besser werden ohne viel Kosten. Wenn wir uns was wünschen dürften, dann wäre das beste Pivot, das uns den Bestcase der Kosten gibt, natürlich die exakte Mitte. äh präzise ausgedrückt den Media an der Eingabe, aber den zu berechnen ist teuer, kann man machen, aber das ist eigentlich auch ein rekursiver Algorithmus, der fast auf Quicksot aufbaut. Äh werden wir hier in der Vorlesung nicht besprechen, aber falls Sie das schon kennen oder nachlesen wollen, es gibt einen Algorithmus Quickselect, der wie Quicksort arbeitet, aber nur einen rekursiven Aufruf macht, der dieses Problem lösen kann. Brauchen sie hier aber jetzt erstmal nicht wissen.

50:00 Ist aber zu teuer, um im Sortieren sinnvoll zu sein. Stattdessen können wir einen kleines Sampel aus der Eingabe wählen und daraus den Median exakt bestimmen mit was auch immer für einer Methode. Das ist dann nicht so wichtig, weil es ja nur ein kleines Sample ist. Und das kleinste sinnvolle Sample sind drei Elemente und stellt sich raus, dass das tatsächlich schon einen hilfreiche Verbesserung gibt. Wir können also das diese Funktion, die das Pivot wählt, die zum obigen Codepasst so implementieren. Wir nehmen drei zufällige Positionen statt nur einer, dann sortieren wir die drei und wir nehmen die mittlere.

50:40 ähm drei Elemente sortieren kann man versuchen cleverer zu machen, aber das lohnt sich wahrscheinlich nicht. Jetzt können Sie fragen, wie sehr kann das denn helfen? Ähm, man kann da die Analyse mit der präzisen Rekursion und so weitermachen, den man äh sich über mathematische Rekursionslösungen hermacht und äh man bekommt dann statt dem exakten Erwartungswert, den Quicksot mit zufälligem Pivot hat, 1,4 Nlogen 1,39 Nlogen, 1,19 Nlogen.

51:12 Ob das jetzt relevant ist oder nicht, dürfen Sie entscheiden, aber der Overhead von diesem von dieser Pivotowahl, in dem man drei Elemente sortiert, der ist winzig. Das heißt, in aller Regel lohnt sich das und praktische Implementierung ähm machen das auch.