[Playlisten] [Impressum und Datenschutzerklärung]

P3B Quicksort, Selection Sort, Bubble Sort; Laufzeitkomplexität

CC-BY-NC-SA 3.0

Nachtmodus Pausen an Schnitten Tempo: 0,5 0,7 1,0 1,3 1,5

Anklickbares Transkript:

die – dritte Praktikumsaufgabe – bestand darin drei verschiedene – Sortierverfahren – zu implementieren – ich hatte gegeben – eine – Liste ein Reh an Frequenzen – von vier hundert vierzig bis acht hundert achtzig Herzen chromatische Tonleiter – aber nicht sortiert sondern quer durcheinander – gab's zur Hilfe auch schon die Anzahl – dreizehn Töne dreizehn Frequenzen darin die sollte sortiert werden und zwar erst mit – Bubblesort und dann mit zunächst sollten dann mit Quicksort – Frequenzen sortieren – das man das Ganze auf dem Wege zu Lautsprecher ordentliches – gesagt auf dem Spiel zu Schallwandler ausgeben kann – dem Andersonsbett – anschließt – Bubblesort – zuerst – an – also was glich diese – Sortierfunktion – übergeben Sie glich das Gerät übergeben – übergeben – hast es eigentlich Anzeige auf das erste – ich kriege die Adresse von dem Eintrag Nummer null im Speicher das ich eigentlich – steht – iTunes – und hier – gibt die Zahl dreizehnter – das oben war auszufüllen – Bubblesort ist ja das – dümmste Verfahren von allen – an – da soll ich was zu Philosophie – sagen weil das noch nicht – überall klar war mit diesem Verfahren implementieren – wann ich persönlich an von außen nach innen zu denken in C von außen nach innen von der – Struktur her von oben nach unten zu denken vom großen zum kleinen zu denken ich denke nicht sofort an irgendwelche Vergleiche und austauschen – denke erst mal drüber nach was ich an Schleifen – habe – und was ich Angriffs habe – Beistrich noch unter Programm aufrufen – ich habe ganz außen erst mal eine Schleife die sagt – solange diese Liste nicht sortiert ist – arbeiten wir – weiter – in der Form und darin habe ich eine Schleife die sagt – ich gehe von links nach rechts durch die Liste durch – und tausche – da konnte das mit dem tauschen wenn zwei nebeneinander – liegen in der falschen Reihenfolge darf sich die beiden gegeneinander aus das da kommt ganz innen drin das tauschen – das überprüfen ob in der richtigen Reihenfolge sind – dann – denken Sie lieber von der Hierarchie – her – erst von großen – mit dem großen Staaten und dann zu klein sind – der Vergleich – und das austauschen das passiert irgendwo in drin versteckt – es vergeht darum ich mache etwas so lange bis diese Liste – sortiert ist und was mache ich solange ich die Liste von links nach rechts durch – ?? von vorn nach hinten oder Visa Komma sie ist mein von null bis zum Ende gehe ich sie durch – die Liste – und gucke auch zwei benachbarte in der falschen Reihenfolge stehen wenn ja tauglich die beiden aus – austauschen haben sie gesehen im Praktikum – geht am einfachsten – und auch am glücklichsten – in dem man noch nebst Variable baut den einen in die Hilfsvariable – den andern in den einen und die Hilfsvariable in den andern – es gibt auch total durch die glatte Lösung wies ohne Hilfsvariable geht aber schreibt kein Mensch ernsthaft per saftigen – Verbrauch nicht zwei Hilfsvariablen – es reicht einiges variabel um diesen – Linktausch hier zu machen – überlege was ich sonst gefunden habe ja das hatten die meisten auch gemerkt im Praktikum – wenn ich immer die Nachbarn vergleiche – ein mit seinen nächsten ein mit seinen nächsten dann darf ich nicht – ihr auch den allerletzten – längs ohne die minus eins dann darf ich nicht in der letzt mit seinem Nachbarn rechtsvergleichenden – Gips nicht mehr den Nachbarn ?? muss sie beim vorletzten aufhören – I darf nur bis zum vorletzten gehen damit ich ihn – mit dem dann allerletzten vergleichen kann – und – solange das nicht sortiert ist auch – das hat dann ja den Gefallen geklappt – an – ich sage erst mal – ich geh mal davon aus es ist nicht sortiert und dann schreibe ich wirklich wörtlich hin solange es nicht sortiert ist – machen wir weiter mit dieser Schleife das ist eine Fortsetzungsbedingung – solange dies nicht sortiert ist – an – wann es ist nicht sortiert es ist nicht datiert solange ich nicht oder höchstwahrscheinlich – nicht sortiert solange ich noch welche findet in der falschen Reihenfolge – stehen – ?? finde ich welche in der falschen Reihenfolge stehen dann merke ich mir – es wahrscheinlich ist es nicht sortiert kann es sein das durchs austauschen dann in der richtigen Reihenfolge steht aber höchstwahrscheinlich – ist es nicht sortiert das merk ich mir – und vorher – bevor ich die Liste von links nach rechts durchgehen – sich eben diese Variable aufbewahrt – und sage wohl mal annehme sei jetzt sortiert – es kann jedem passieren – und wir typischerweise passiert das über welche finde – die nicht in der richtigen Reihenfolge sitzen und stand merk ich mir es war nicht sortiert – so ging dann – Bubblesort – ich habe was dazwischen geschrieben was sie vielleicht – irritiert – Punkt – für diese Laufzeit – Komplexität – erweckt keiner was zu sagen – das war wirklich festzustellen – dass eine Zusatzaufgabe – Komma ?? Komma mitzählen – diese Vergleiche gemacht werden dann hat man – Hausnummer wie viel – Zeit das ganze läuft – Zähler mit für jeden Vergleich – sind vor dem wir für jedes Eve das sie stattfindet zähle ich einfach mit das habe ich hier in der freigesetzt – damit es aus dem Code rausnehmen kann wenn ich hier – das rausnehme – sehen sie ist diese Variante kann und nicht da – und ist dieses hier nicht da ganz ganz normaler Code – in die nicht gezählt wird – so – muss aber gerade laufen lassen der Witz bei der Soundausgabe – ist ja – auf mal – das kann man jetzt führen also sie haben hoffentlich im Praktikum ?? diverse Fehler gehört – begrenzen die gar nicht vorkommen dürfen – und andere Scherze – an – das hübsche ist das man jetzt zuhören kann was passiert – irgendwo wird der größte stehen in dieser Liste und der größte wird automatisch – beim ersten Durchlauf – sinnlich das vertauschen immer wieder mit den Nachbarvergleiche – mit der Größe automatisch hinten landen – von ist doch ziemlicher Unsinn der tiefste wird dabei irgendwo stehen bleiben typischerweise – irgendwo in der Mitte der wirklich sofort unter unten landen – beim nächsten Durchgang – wird der zweitgrößte – nach oben aufsteigen – der tiefste wird – leichter einen runter gehen sieht man dann – dann – auf jeden Fall wird und noch ziemlich viel Unsinn seiner ?? muss also hören dass das obere Ende allmählich fertig wird da habe ich dann – die höchsten Töne in aufsteigender Reihenfolge – und unten muss es doch schon bisschen durcheinander sein die tiefen Töne die steigen langsam ab Komma zumal – was ich ausgebe ist ja – nicht – was ich ausgebe – hier in meiner Soundfunktion – ist ja nachdem ich einmal von links nach rechts durchgegangen bin – gebe ich die Liste aus und danach eine kleine Pause – also das obere Ende muss sehr schnell fertig werden – und mit dem es wird Töne haben die langsam – absteigen tiefe Töne die langsam – um ?? die Tonleiter ist fertig – ?? resultiert – es – gibt doch einen Extradurchgang – am Ende weil ich plötzlich aus dem soll – man hier noch mal steifer eingebaut habe – also mal auszugeben – das wäre Bubblesort – Selektionsort – dann – der Gedanke hinter Selektionsort – ist – das ich aus der Liste – mit den kleinsten raus suche – eine ?? ihr Minimum – und den nach unten tausche – steht der kleinste der unten – und was vor Anstelle null Stand steht irgendwo in der Mitte – dann mache ich weiter mit dem – oberen Teil im rechten Teil der Liste – lasse den untersten Weg ist es richtig das steht schon der kleinste – aus dem roten Teil durch den kleinsten und tausche den nach unten und so weiter – und so weiter – das ist Selektionsort – war ein Aufruf von derselben Sorte – dann – Ida von außen nach innen gedacht was macht die äußerste – Schleife das äußerste Eve – ich gehe – von links nach rechts durch – um – den jeweilig – linken zu bestimmen – eine Schleife die im Durchgang Nummer null – ?? den hier bestimmt das Minimum vor allen – eine Schleife die im Durchgang Nummer eins Linie bestimmt das Minimum von allen bis auf den Notnummer null und so weiter – und so weiter – ein Schleifen jeweils in den unteren bestimmt – die muss nicht alle angucken ?? es reicht wenn die beim vorletzten aufhört – denn wenn sie alle richtig haben bis auf den vorletzten – dann ist der letzte automatisch festgelegte – Muster stimmen – die geht also alle durch bis zum vorletzten wieder mal – das – ist diese Schleife und sucht den kleinsten – in den verbleibenden – dass es diese Schleife in den Bildern rechts stehen – in den rechten deiner Liste suche ich den kleinsten – ich merke mir erst mal einen Kandidaten – das wäre der Wert des Kandidaten – und das wäre der ?? die Position des Kandidaten die Position trotz ?? für das austauschen – reichlich minderwertigwilligen – Wasser wieder hinstellen – zwei gegeneinander austauschen – ich will was eine Position reinschreiben – ich brauche nicht nur den Wert ich muss auch wissen an welche Position ich nachher was reinschreiben muss – dann – die Bestimmung des Minimum ?? sicherten Kandidaten – und ich gehe den Rest der Liste durch seine Daten im unteren – typischerweise – Stimmerwägungen – muss ich starten dass es ein Kandidat der der jetzt an der Stelle I steht – wonach er der Kleinste stehen soll – natürlich – dass ich diesen Kandidaten miteinander vergleiche – wieder meinen Zellfunktionsvergleich – wenn ich einfinde der kleine ist merklich mehr in der kleiner ist als Kandidat – wenn ich den fertig bin bin ich aus – dieser rechten Liste den kleinsten gefunden habe – dann tausche ich mit dem unteren der untere war bei I und der kleinste Stand bei – Minimumsindexes – hab ich mir gemerkt wo der kleinste Standard – im Wert von dreizehn habe ich schon vor gespeichertes ?? komm ich hier ohne – Hilfsvariable – aus – und die Soundausgabe einfach jedes Mal – nachdem der jeweils kleinste bestimmt ist das heißt was man jetzt hören muss – ist das lustigerweise – das ganze vom unteren Ende – stimmt – im ersten Durchgang – stimmt sofort – der aller erste im zweiten Durchgang stimmen die beiden ersten und so weiter – und oben sind nur noch welche die höher sind – Staff oben ein ganz tiefer Ton erscheinen – die stehen ziemlich wild durcheinander – aber sie dürfen nicht zu tief sein in die tiefsten sind schon gefälligst unten einsortiert – zwischen – den beiden da das – Unternehmen ?? drei – oben ist es total wild – das – aus – ?? – bei dem – Selektionsort – habe ich jetzt ja – nicht so was raffiniertes drinnen – wie bei dem Bubblesort – bei dem Bubblesort sage ich irgendwann wenn's sortiert es darauf – an – bei dem Selektionsort – mal das wirklich auf brutale Weise ich bestimme den aller untersten den vordersten dann den zweiten – den dritten und so weiter – ohne wenn und aber selbst wenn die ganze – Liste schon sortiert sein sollte Gerüche brutal – durch – Das heißt – muss nach einer mal an das Verfahren sowie Sätze geschrieben habe ?? immer dieselbe Laufzeit ist auch immer genauso viel Stück schüttet selbst wenn ich mit der sortierten Liste reingehen – dann – nur dass dies – so lange durch Wies glaubt es müsse die durch Nudeln immer dieselbe Zeit – an – der Stelle ?? Komma was zu – Bubblesort sagen auch das ist noch nicht die – hundert Prozent – in Anführungszeichen – optimale Implementierung von Bubblesort – was ich hier nicht benutze ist zum Beispiel – das am Ende – das schon die höchsten automatisch stehen nach dem ersten Durchgang muss ich nicht bis hinten Babbel bei der Hoechst ja schon fertig ist nach dem zweiten Durchgang muss ich noch ein Swing erwerben und so weiter – Ehrlich könnte man das sie noch anpassen einige von ihnen hatten das gemacht – das hätte das Verfahren nicht aber ist wäre – minimal schneller als ein Möglichkeiten ohne Fehler einzubauen deshalb ist bei dir sogar nicht machen – aber theoretisch könnte man es machen könnte theoretisch sogar auch nicht bei null anfangen – und feststellt dass die untersten schon sortiert waren im Durchgang davor – da muss ich nicht ganz unten anfangen denn die waren ja schon richtig als hier könnte man auch noch was ändern – wie gesagt das wird es nicht retten macht es nur bisschen besser – zurück zu Selektionsort – habe ich eben gar nichts von der Sorte drin jetzt – das man irgendwie noch – Kniff einbaut – und schneller zu machen wenn's schon sortiert war oder wenn's gerade günstig ?? – der – dritte im Bunde Quicksort – Quicksort ist nun ein Verfahren das der tatsächlichen wahren Leben vorkommt – uneins – dass man auch gut falsch programmieren kann – man sie gemerkt im Praktikum das es echt hart – ahnen – bis man das Wiki zum Laufen kriegt sitzt man da doch – mindestens eine Stunde dran weil – irgend ein Unsinn mit einer zu viel zu wenig passiert garantiert – ich gleich nachher auch normale – echte Implementierung – von Quicksort ist in der Bibliothek aussieht – in der Bibliothek ist er nämlich gerne – alles professionell – sagen zwei Wochen lang entwickelt worden ist ?? drei hundert langen ?? geworden ist dann ist schon sehr anders aus als Ganzes nicht nur das reine Quicksort sondern man hat am Ende dann gerne auch noch ein anderes Verfahren – um die allerletzten – noch schneller zu sortieren Quicksort es gut wenn man sehr viele hat – ähm – mit Einschränkung sie gleich noch was sagen muss was Basteltag angeht die – Rekursionstiefe – ist – alles mit schwieriger soll ich das so vorstellt – ?? Bibliotheksrede – im wahren Leben – implementieren Sie bitte keinen dieser Funktion selbst das wäre völliger Blödsinn ist es erstens gefährlich – an – weil man es nicht so gut testen kann wie die Notizfunktion – die man sowieso hat auch in zehn – die Überdiskussionen – ist von – zwei Millionen Leuten verwendet worden die ist relativ gut getestet – ihre eigene der beschriebene Funktion hatte selbst mal Zimmer durchlaufen lassen dies nicht gut getestet – und außerdem sind die Bibliotheksfunktion – extrem – optimiert – nicht zeitgleich nochmals erhöhte Funktion aussieht ist wirklich – haarsträubend – an – ich kann einen Grund erkennen weshalb man es selber baut – die benötigten Summen sind so haarsträubend dass die relativ viel Speicherplatz verbrauchen wenn ich es ohne magere Maschine habe wie das Prinzip auf dem Notepad – mit nur zwei Kilobytes – Programmspeicher – endgültig aus dem Grund überlegenes – selbst zu programmieren – dass ich ?? extrem – schlanke Variante – von zum Sortierverfahren – bauen dann ergibt es Sinn alles andere – möglichst nicht ?? Finger davon – insofern ist das die einzige Übung für Algorithmen das ist nicht wirklich selbst programmiert – sondern – Übung – über solche Algorithmen nachzudenken – wie würden Sie vorgehen wenn – Vorräte – hierfür Quicksort Quicksort an – ein rekursives Verfahren das ist – haarsträubend – das Verfahren ruft sich selbst auf ich manchmal aufwies – funktionieren soll – der Grundgedanke – ist relativ – einfach – besser hinzuschreiben gesamte gemerkt ist – eine mittlere Katastrophe – der Grundgedanke ist die Liste – grob zu sortieren in groß und klein – ich werde mir irgend ein Element der Liste – und sortiere die Liste dass alle die kleiner sind – nach links kommen – und alle die größer gleich sind nach rechts kommen – oder kleiner gleichen größere muss man sich ein – kleiner größer gleich – nur grob sortiert – nicht aufsteigend – und dann – ruft die Funktion sich selbst auf eine Rekursion – mit dem linken Teil der Liste macht sie dasselbe – sie sucht sich – aus dem linken Teil der Liste – ein Element – und sortiert diesen linken Teil grob – all die kleiner sind als das Element und alle die größer gleich sind das Element so in die Wahl gestellt ?? dass er wie auf der rechten Seite – und so weiter – und so weiter – und wenn man das hinreichend oft macht – die Liste sortiert offensichtlich – das ist der Gedanke bei Quicksort – und die Hoffnung – ist das man hier – üblicherweise – fifty-fifty – Trend – wird man im wahren Leben nicht das kann gehörig schief gehen aber die Hoffnung ist das es so Pi mal Daumen fifty-fifty – ist das was sie wird fortlaufend halbiert – man ist sehr schnell – nach wenigen Zügen sozusagen nach wenigen Iterationen – fertigte – soweit – das Prinzip – das umzusetzen ist – eine andere Geschichte – erste Frage wo nehme ich – dieses Element her mit dem ich links und rechts bilden das ist er sowieso der – französisch Pivot – oder Englisch bewirkt – Angel Punkt der Drehpunkt – vornehmlich dieses Element her – es – liegt irgendwie so nah das aus der Mitte der Liste zu nehmen vor allem das ganze schon happig sortiert ist – das gute Idee das aus der Mitte der Liste zu nehmen habe ich wirklich das in groß rein getrennt – zum Programmieren ist das nicht so hübsch – beim Programmieren ist es am einfachsten – einmal anzunehmen zum Beispiel den untersten einfach zu ich nehme die Nummer null und vergleiche alle mit der Nummer null ?? gesagt schöner wäre in der Mitte zu nehmen also was man eigentlich dann machen solltest folgendes als ersten Schritt das ?? sich eingebaut – als ersten Schritt vertauschte ich die Nummer nur den in der Mitte – dann arbeite ich soweit ich das jetzt sage – das ich die Nummer null als – Bild verwenden – ?? gibt's – zwei – Strategien – im Groben – wie man vorgehen kann ich kann mit einem Zeiger – von links und einem Zeiger von rechts ankommen – und sagen – mit dem linken Zeiger wandere ich so lange – bis sich ein Element gefunden habe das eigentlich nach rechts gehört das also größer gleich ist – wenn ich soweit gefunden habe wandere ich mit dem rechten zeigen in solch einem Fall war – an der ich mit dem rechten Zeiger so lange bis sich ein Element gefunden habe das einzig nach links gehört was kleiner ist – und dann tauscht die beiden aus – ist dahin von da und da ist dann aber schon okay – Marie weiter – gucken wir weiter auf der linken Seite auf ?? eins finden was zu groß ist – mit eins finden Suchende auf der rechten Seite eins was zu Bein ist dann tauschen die beiden aus – bis sich die Zeiger irgendwann treffen – das ist lustigerweise – auch die Art wie Quicksort umgesetzt ist in in der ?? benötigt und so nicht Kleinanzeige – bei mir geht das grundsätzlich schief ihr Fall – plus minus eins mit den Zeigern – verständlich was daneben haut am – ich finde – eine alternative Implementierung – lustiger die kriege ich sogar hin typischerweise – ohne – mich in das minus eins Sachen zu verstricken – ist nicht ganz offensichtlich die Segmentierung – hier mit zwei Zeigern – einer Frühlings einer von rechts ist relativ offensichtlich die an der Implementierung sicher zeigen ist nicht so offensichtlich – aber ich hoffe man sie einmal verstanden hat – ist – sie leichter umzusetzen – ich suche – alle durch – außer den Nummer null natürlich – außer Nummer null ?? suche ich alle durch nach einem – der Zug Laien ist – wenn ich die Anfänge der zu kleines tausche ich den Ausschnitt Nummer eins Komma null bei der ?? wird – dann suche ich weiter – sich – noch meinen finde der zu klein ist – den Tausch sich aus mit Nummer – zwei – steht da unten und so weiter bis sich am Ende wird das ?? for-Schleife – die von der Nummer eins Nummer null ?? über die von der Nummer eins bis zum Ende geht – und nach Elementen sucht die zu klein sind kleiner Zettel wird – sobald diese for-Schleife ein Element findet was kleiner als über des Schatzes das erst in den Nummer – eins das nächste was es findet die Nummer zwei das nächste was – Nummer drei – und so weiter – dass er sich auf einzeln einer Forscher von Japan zweiten Zähler – der mir sagt wo denn das nächste Element von oben – gefälligst einsortiert werden muss – das wenig leichter zu implementieren ?? habe ich weniger Ärger mit irgendwelchen Sachen iso plus minus eins Fall scheint – so – sieht's dann aus das mit der – Magie an der innere Teildrucke – der Wert von dem wir mit Element – ?? zwischen Caddy und noch immer X von null schreiben können – würde man eigentlich machen – Komma so ist klar was ich meine – dann – Struktur von außen nach innen das ist die for-Schleife – die – hinter dem ?? wird durch Betätigung sich alle an nach dem ?? wird – geguckt sich alle anders ist es grün und das Grün ist meine ?? habe ihn – mir alle an ob sie denn zu klein sind – kleiner als der wird – wenn ja wird ausgetauscht – sehen was dieser rote Zeiger ist der rote Index – ist genannt – wenn ich einen finde der zu klein ist Tauschicht aus gegen den eine Fälle Split und Split zeigt dann – nach dann auf den nächsten – so billig ist das das hier ist denn jetzt der Kern von – Quicksort nicht das so mache ich mit einem rechten Zeiger – sondern auf diese etwas raffinierter als – nicht ganz fertig bin – muss sicher noch dafür sorgen – dass der Gewinner in der Mitte steht – schließlich am Anfang etwas ungeschickt also ich hab hier danach ?? irgendeine Sortierung – nach dem das durchgelaufen ist der P wird der Rest angefasst worden ich hab welche diesen Tag kleiner kleiner größer gleich größer gleich größer gleich größer gleich größer gleich – der ?? wird gehört aber in die Mitte – das muss ich noch machen – das Leerschritt hiernach – das darf ich aus – jetzt – habe ich meine Soundfunktion – nach dem austauschen einmal abspielen – und dann kommt dieser rekursive Aufruf die Funktion ruft sich selber auf – das – FA wie es ist aber nicht in der vollen Länge sondern bis – eins folgende wird – das ist dieses hier den linken Teil sortieren – und dieses hier hast den rechten Teil sortieren – was übrig bleibt – ein Sanity-Check – ist folgendes – die Gesamtlänge – die hier sortiert werden muss – ist die ursprüngliche Länge ab minus eins der Lebensmittel – nicht mehr weiter sortiert ich sortiere links ich sortiere Beistrich dass irgendwo – ich sortiere links ich sortiere rechts – diese beiden Längen zusammen addieren haben Sie die Originallänge – minus ein – ?? was nicht hin – die zusammen addieren längst wieder Split – plus Flatszins – beträgt minus eins längstens eins einsehen dass die Gesamtlänge so muss es sein – und – harte Schreibweise soll ich noch erzählen – dass man ihm gesagt X – der Name eines Gerätes gleichzeitig ein Zeiger auf den Eintrag – null – dass sie ist ein Zeiger auf den vordersten Eintrag im ?? sei und wenn sie dann einfach Draufallianz – Zeigerarithmetik – wenn sie das einfach zusammen ihren Anzeiger – an die richtige Stelle – Komma sogar kein neues Regen wieder zusammen zu fummeln sag einfach nur aus dem bestehenden Ray – gehe an die Stelle Split – das ist die Rekursion bei Quicksort – und das was nicht vergessen darf bei Rekursion – wenn die Funktion sich selbst aufruft – hatte ich auch hier unter Praktikum gesehen ?? die Funktion – ruft sich selbst auf sogar zweimal – die Funktion ruft sich zweimal selbst auf – diese Aufrufe rufen sich selbst auf – und so weiter – irgendwann muss es stoppen sonst haben Sie hier – die Kettenreaktion – irgendwo muss dein Ende sein – der muss jetzt sagen so fertig sonst haben sie acht – sechzehn zweiunddreißig – und so weiter im Busstopp sein – das muss immer eingebaut sein jede solche Rekursion – sie können nicht weiter immer weiter die Funktion selbst aufrufen – davon nicht vergessen – und das habe ich – hier eingebaut – ?? wird es auch unten einbauen das man hier sagt okay wenn – die Beteiligten – die hier zu sortieren sind zu kurz sind wenn sie nur ein Element haben jeweils – Listen mit einem Element muss ich nicht sortieren – wird man auch hier sagen – wenn ich – ein Element – nur sortieren muss – dann das Wasser sein oder sogar nur null Elemente sortieren musste ruf ich Quicksort gar nicht mehr auf jährliches anders gemacht – in dieser Zementierung ich rufe es dann auch auf auch wenn nur noch null – Elemente zu sortieren sind – sachliche oben beim Einstieg in die Funktion – wenn ich – ein Element oder weniger zu sortieren habe in der Liste dann lassen das aber sofort sein ?? ist sie schon sortiert eine Liste mit einem Element ist datiert ?? ist mit null Elementen – ist in gewisser Weise auch sortiert – dass sie oben eingebaut – dass es die – das Ende der Rekursion – irgendwo muss Feierabend sein bei der Rekursion und bei mir ist das hier – ohne das – kriegen Sie – eine immer größer werdende Kaskade an Funktion aufrufen – das wäre nicht im Sinne des Erfinders – gab es viel zu erzählt am – in der akustischen Ausgabe – ist das nicht mehr ganz so klar zu erkennen je Spiel jetzt immer die Teillisten – ab – also einmal trinkenden Gesamtausgabe – das ist der erste Aufruf – und dann kommt – dieser Aufruf – für – für den linken Teil für den linken Teil kriegen wir dann die Ausgaben nur des linken Teils – und dann kommt hier noch mal diese Aufrufe den linken Teil vom linken Teil also dann nur der linke Teil Familientag ausgegeben – und so weiter – das ist nicht mehr ganz so klar zu – erkennen was da passiert aber sie haben's gemerkt im Praktikum wenn dann total falsche Frequenzen auftauchen – müssen sie immerhin Punkt sie haben mal wieder eine Stelle gelesen werden – dürfen oder auch das auch gerne zu hören war ganz viele gleiche Frequenzen sie haben gegenüber dem Kopieren hier – ja sie haben – etwas über kopiert aber nicht ausgetauscht – das ?? sondern auch relativ schnell – mal wie es sich anhört – immer kürzer wird weil ?? Beteiligten habe – und fertig aber es hat mich von der Sound Ausgabe ja schon klar wie schnell das was es absurd schnell – typischerweise – muss man sagen – in Mittel – ist das extrem schnell – es kann schief gehen – wenn – wir mit immer gerade so ungeschickt gewählt wird – dass ich nicht wirklich die Liste Teile – dann – so – wenn der Sohn geschickt für das die Liste nicht fifty-fifty geteilt – sondern dass sie – null zu hundert geteilt ist beim nächsten Mal schon wieder nur zu hundert ?? wenn das häufiger passiert habe ich nicht das Problem das kann insbesondere passieren wenn die Liste in gewisser Weise schon vor sortiert ist sehr unglücklich versandet worden ist – dann dort Quicksort lange – aber im Mittel – getwittert extrem schnell – dass es ein Vorzug – und jetzt sage ich mal – den Nachteil von Quicksort – habe ich gelernt beim Testen – bin ich hier mit – einer sortierten Liste reingehen – das erste Lexus fortlaufen – die Liste sortiert ist wirklich mit der sortierten Liste in Quicksort rein – Quicksort ich geschrieben habe kann extrem schlecht mit sortierten Listen umgehen – an – Komma was da passiert – so – ?? meines letzten Sorten rein und durch – ?? Ausgaben sei so – aufräumen – so – oder – so die Liste ist jetzt sortiert und jetzt gehe ich mit der sortierten Liste – in den Quicksort rein – es wird lustigerweise – absurdes passieren – baltische zu kleines – sich immer rein in fix und – ?? prüft erst mal aber schon abbrechen muss habe ich überhaupt noch nennenswert was zu sortieren – soweit – durch – geht jetzt von links nach rechts das als besondere Situation mal – weg Punkt einige Umsätze ?? Punkt – an der Stelle – durch – ?? wird sich gleich rekursiv aufrufen – hier unten mit der sich selbst wieder aufrufen – das heißt wenn ich jetzt sage weiterlaufen – weiterlaufen – welche oben stoppen – da wo sich selbst aufgerufen hat – die Ausgabe von dem ersten Teil jetzt habe ich die linke Liste – sind Baulänge – null die linke Liste hat die Länge null neuer Verein – das heißt die Gitter sofort wieder raus – gerechte Teil der Liste hat die Länge zwölf – was es genauso – neben die unsinnige Situation sich gegen ?? gesagt ?? verwendete wird immer genau an einer Seite steht ?? fast genau an einer Seite steht – dann wird das Verfahren sehr uneffizient – das aber jetzt der rechte Teil ist – zwölf lang – das war der rechte Teil ist der linke Teil von dem rechten Teil ist wieder null lang – voll – und der rechte Teil von rechten Teils elf lang – und jetzt wird's spannend – ?? Stackpointer – Vorstag – Stack – ist auch seitens der Greenwich – sehr generelle Sklave Single bei dem nächsten Aufruf – auch noch – nach – jetzt hören Sie – der Eintrag Nummer elftes acht und der Eintrag Nummer zwölftes acht – werden das liegt daran dass diese Maschine so klein ist – wenn ich ein wenn eine Funktion eine andere Funktion aufruft – wird in Imst auf dem Stack dem Stapel auf dem Stack abgelegt – wo in denen wir zurück müssen – von Wohnen gekommen sind für jeden weiteren Funktionsaufruf – muss das abgelegt werden das es werden auch – Variablen abgelegt und was anderes jeder Funktionsaufruf – in einem Funktionsaufruf – koste Speicherplatz – und – das ist der Ärger mit Quicksort durch diese rekursiven Aufrufe frisst das Ding Speicherplatz – an einer Stelle an der man es – normalerweise nicht vermuten würde durch diese Aufrufe der Funktion alleinig lege nicht ausdrücklich weil der Platz an reservieren ich ausdrücklich Speicherplatz und es passiert – indirekt – durch die Rekursion – jeder Funktionsaufruf – im Funktionsaufruffrist – platzt – und sie sehen – das passiert auf so eine Weise dass er mir das Gerät kaputt macht – die Bein Speicherbereiche – wachsen durcheinander – und damit ist das Gerät plötzlich kaputt – dann – also Vorsicht mit Quicksort auf seiner kleinen Maschine und nicht nur da habe man richtig massive Datenmengen – hat ist das offener groß Maschine genauso Ärger – ein schnelles Verfahren – aber Rekursion hat – ihre Tücken – des Steck kann zu groß werden – die Rekursionstiefe – kann zu groß für – und – an der Stelle kann ich nur gerade zeigen wie denn das offiziell – aussieht ✂ dass der Quicksort wie sie ihn in Linux finden wir da eingebaut ist Komma netterweise ja durch den Kot einfach angucken – dann – die gibt's ein Makro – sehen das es sie mit dem Präprozessor gebaut ein Makro mit dessen Hilfe man Sachen austauschen kann – offensichtlich auf eine Art sich noch nicht gezeigt habe das sieht schon sehr – durchgeknallt – aus – die Fonds auch anders schreiben – an den sie schon ?? optimiert durch Bibliotheksfunktion – sind der Kern sie im Traum nicht traut sowas zu schreiben – um zwei Sachen auszutauschen – und und und und sie sind Kleinerklärung – ist der funktionieren – soll – Komma hätte sie sich in sechzig groß Quicksort – sehr allgemein – der sonntäglichen – Thatchers der sortiert was auch immer man will – ich muss sagen wie groß sie für Beitz diese Sachen groß sind dich sortieren will wie viele sind wo sie stehen – und ich muss so eine Funktion angeben – die zum Sortieren dient – dann die Fusion kann zum Beispiel sein alphabetisch sortieren – nicht Zeichenketten sortieren will statt – ganzer Zahlen all das ist frei einstellbar das macht das ganze auch wieder langsamer – allgemein verwendbar aber auch wieder langsam an das wäre wieder ein Grundwasser bundesweit selber Programm möchte – das Bundes – genau zugeschnitten hat auf das was man haben will – und der kernigen – ganzer Gruppen sie sind das ist – etwas länger als das was – er eben bei mir stand – ?? hier als Techno MT – eins Zeiger – links ein Zeigerrecht – jetzt endlich auch Zeigervariablen – anders als bei mir niemals aber nur – Nummern Indiz ist diese Zickigzeigervariablenanzeiger – Linksanzeige – rechts – Punkt erst mal wurde im ?? wird sinnvollerweise finden soll er nimmt nicht irgendwo ein sondern sucht erst mal wurde in den Frauen findet – und hier kommt mit Ankündigung – zu sagen ist FMS Kollaps der Wortsection – an mit Anbindung kommt hier diese Schleife – wir gucken von links aufs einen gibt der zu – großes – gucken von rechts auf einen der zu klein ist – und dann tauschen wir unter bestimmten Umständen aus Semikolon – was es hier noch alles Mögliche – das ist es was ich meinte mit plus minus eins richtig kriegen das es heftig – Komma dass genau haben will – aber das ist der Kern von Quicksort hier in dieser allgemeinen Form geschrieben in der Bibliothek Funktion müssen sie nicht verstehen ich wollte die Nummer gezeigt haben damit nie die haben – dann – womit sich denn – diese Leute die Linux und so weiter bauen dann tatsächlich auch mal zu beschäftigen solche Sachen ordentlich zu implementieren – superschnell – super allgemein – sehr sauber zu implementieren – assoziiert ist das es kein reinrassiger Quicksort ist – am Ende hatte noch in einer Sortierverfahren – Wetter noch paar Elemente über sind – Satire nicht Quicksort sondern – sortiert mit ein Verfahren das sich ins Taschensortiment – Punkt nicht so wie sie Spielkarten sortieren würden in den Stapel – in der entstehenden sortierten Staffel – einsortieren – an der richtigen Stelle – es ist effizienter Mann weniger hat der Schatten irgendwann um nur ganz wenige drin sind Ritter um und macht diese Sortierverfahren – einer der wesentlichen Tricks und anderer Trick ist dessen diese Rekursion selber baut an – Komma dass – Sehen Sie sowas wie Stack Zeiss – pusch und Popp – diese Rekursion baut das Teil alleine es verlässt sich nicht auf den Prozessor – mit der üblichen – mit den üblichen – Funktion – Rücksprüngen – sondern des Bau des selber das es effizienter – als das haarsträubend das würde man das normalsterblicher – schlicht und ergreifend – so nicht hinkriegen – des Mannes ein halbes Jahr dran bis das ordentlich läuft – dass es das Plädoyer für Bibliotheksfunktionen – wenn sie Sortierfunktion – Suchfunktion – und was auch immer – kartographische – Funktion in der Bibliothek Hand nehmen sie die aus der Bibliothek – nirgends anders her oder versuchen sich erst bei Bibliothek – basteln sie alleine so nicht – jetzt – Komma zur Laufzeitkomplexität – wie kann ich sagen – ?? ist allgemein das Bubblesort – und der – Selektionsort – eher von der langsamen Sorte sind – und dass Quicksort ihr von der schnellen Sorte ist – für diese Anwendung hier – dreizehn – Zahlen sortieren ist mir das relativ – Schmerz das läuft – schnell genug mit allen Verfahrens – in Sekundenbruchteilen – solche Überlegungen sind spätestens dann spannend – zum Beispiel wenn Google – eine Million Suchergebnisse sortieren muss nach – Herrn – danach was will was gute Suchergebnisse sind und was schlechtere Suchergebnisse – sind und das nicht nur für sie eine Million Suchergebnisse – parallel für – eine Milliarde andere Leute auch noch machen muss damit das spannend – spätestens da wird das Band – schon weit vorher spannend Komma – glaube das offensichtlich da macht man sich Gedanken drüber – läuft das – in – zehn Millisekunden – oder läuft das in – hundert Nanosekunden – das schlecht sich da schon extrem nieder – allein schon im Stromverbrauch und ?? zur Wachmann installieren muss – alles um sich drüber nachzudenken ab einer bestimmten Stelle – um sich Tor nachzudenken ob man schnelle Funktion oder langsame Funktion hat – diese Beschreibung – schneller langsam die sogenannte – Laufzeit – Komplexität – ist es denn in der Informatik – die Laufzeit Komplexität – abstrahiert – von der echten Laufzeit man gibt nicht genau an oder dauert jetzt – drei Millisekunden – sondern man gibt eine Ordnung an – das will ich mit Ihnen ein bisschen – wie armselig soll es am einfachsten Wasserwechsel sorgt immer gleich lang läuft so wie ich ihn gebaut habe – dann – zähle man nicht ausdrücklich durch wie viel Millisekunden das sind aber das könnte man auch – mit einem Profaller – sind die typischen Wicklung Umgebung eingebaute Pro verlangen tatsächlich dann sagen dieser Fonds uns auf ?? hat zwanzig Millisekunden gedauert – ?? sowie das gar nicht haben die theoretischen Worte geht anders dran wie gesagt es geht einfach nur um Ordnungen – im Vergleich was das bedeutet – möchte nicht mitzählen wie viel Millisekunde sind ich zähle einfach nur welche Befehle das sind – und auch nicht mal das das spannende bei den Sortierverfahren – ist die für Vergleiche ausgeführt worden sind – wenn ich viele Vergleiche ausführen – spricht das dafür dass das Verfahren super langsam ist – nicht tausend Vergleiche ausführen statt fünf hundert wird wahrscheinlich die Gesamtdauer – auch – ungefähr zweimal so lang sein – wie bei den fünf hundert – das sollte ungefähr proportional – sei die Zahl der Vergleich und die Laufzeit – und was sich hier leichter zu ändern ist die Zahl der Vergleiche deshalb will ich mich herausreden – und gucken mal nur – nach der Zahl der vergleiche – wenn sie Aufgabe für sie jetzt – wenn sie – en Elemente hier haben eine Liste aus N Elementen – wie viel Vergleiche – wird Selectschutzort – machen – wenn Elemente wie viel Vergleiche wird Selektionsort – machen – was es ist leichter mit N hinkriegen – was ist wenn es fünf werden die Komma dass ausgerechnet – ich mit fünften reingehen – wie könnte ich ausrechnen abzählen – wie oft er hier – Vergleiche macht – mit fünf Elementen reingehe das mal Klammer auf ✂ damit fünfundneunzig – schon hin – ich habe meine – Fragen – so – den untersten – nämlich als Kandidaten für das Minimum von allem – und vergleiche – ich Kandidaten für das Minimum von allen mit dem – mit dem mit dem mit dem – sie beim ersten Durchgang um den untersten zu bestimmen – vier vergleiche – dann ist der unterste fertig – ich nehme den Nummer eins – Nummer null bei der untersten Nummer eins – ?? als Kandidaten für das Minimum von den verbleibenden – diesen Kandidaten – vergleiche ich dreimal und so weiter – zwei – eins vier drei zwei eins zehn Stück – sind Vergleiche für ähm gleich – fünf – sechzehn – Vergleich heraus – die Frage ist was allgemein passiert und eine Ziffer Verfassung geometrisches Muster auf mal mich vier drei zwei eins – das angucken – ?? ich starte – ?? Wasser mit vieren auf – in gleich fünf König dieses gleich fünf – vier – drei – zwei – eins – wie können sie da auf die Schnelle zählen – kann schon geringer geworden so können Sie diese Kringel – auf die Schnelle zählen ✂ sie – machen das zum Quadrant Quadrat könnte vielleicht erzählen müssen bisschen gucken ich ergänze noch ?? Diagonale – wenn das so – ich ergänze noch ?? Diagonale – und jetzt – nämlich diese schwarzen Punkte noch mal – aber hier – ist eigentlich was der kleine Gauß informelle von – Geschichte – Zahl von eins bis hundert auf zwei Tieren – dann – Sinn ich habe genauso viele schwarze Punkte wie grüne Punkte und dazu kommt noch die Diagonale – müssen es jetzt mal hier Anzahl der vergleiche – Anzahl vergleiche – das ist ja die Anzahl der schwarzen Punkte – ist also – ?? sang jetzt mal diese Punkte sind es denn jetzt die schwarzen ?? nicht allgemein in habe ✂ sie nähen das ganze Quadrat – in Quadrat – ziehen die roten Abwehr sind ähm zwei ?? für fünf die Länge der Diagonalen in Quadrat minus N – dann habe ich die schwarzen und die grün – dann noch die Hälfte in Fahrradinhalte – oder – wenn mal N minus eins – Halbe können ja mal gerade hier ausprobieren in der fünf fünf mal vier durch zwei sind fünf ?? zwei sind zehn – einmal in minus eins halbe – eine von tausend Arten die man so was aus mir kann als zweites treiben sie irgendwann was aus – mal gemacht was man das auswendig – ich überließ mir – mit zum Quadrat wenn ich sicher weiß oder man kann's auch zu Fuß in Schreiben eins plus zwei – plus drei plus vier das ist die Legende von – vom kleinen Gauß dass er gesagt hat gucke ich nämlich hier nach da und ich nehme die drei nach Damen sehen Sie das ist fünf plus fünf – fünftens ist nicht ganz so klar wie das mit hundert machen als Busfahrt des weiblichen – an und John fand man mit hundert neunundneunzig und so weiter neunzehn hundert eins bis hundert eins – bis ein – tausend Wege fürderhin – in – Madrid also an dieser Stelle netterweise – eine geschlossene Formel so viel Vergleiche – wird der Selektionsort – in dieser dummen Implementierung – machen – für – N Daten wieder reinkommen – uns – in der theoretischen Informatik gibt man – nicht dieses an das es ja sowieso auch schon – gelogen war das die Anzahl der Vergleich ist das nicht die Anzahl der – Taktzyklen – jeder Prozessor braucht schon geistig an seinem Millisekunden – oder sowas sondern das ein schon recht abstraktes Maß dafür ?? wie lang diese Funktion läuft – man ?? jedoch weiter das sowieso so abstrakt – Komma was noch weiter abstrakt – und man sagt nämlich das hier ist – groß wovon – in Quadrat – groß Os eines der All Landau Symbole – bei der Landau die populär gemacht hast davon gibt's noch fünf – für die Tele fünf andere – Sonne gibt doch klein O – Omega und Großstädter und alles mögliche – groß O ist der – am häufigsten vorkommt – es ist von der Ordnung in Quadrat und das gibt man den üblicherweise – als – Laufzeit – Komplexität – des Algorithmus an Ofen in Quadrat die Laufzeit – wächst quadratisch – das ist damit gemeint – man – muss über das quadratische wenn sie diese auseinandernehmen dann sehen Sie das das ist ja – in Quadrat halten minus N halbe – ein Vielfaches von in Quadrat – und etwas – das im Verhältnis – Radikalent – vertrat bestimmt das Wachstum in den gleich tausend haben eine Million – halbe – tausend halb ist dagegen ein Witz – wenn sie endlich eine Million haben – eine Billion halb und hier hinten eine Million halbes im Verhältnis noch viel weniger – auf lange Sicht gewinnt dieses ähm Quadrat – mal irgend ein Faktor – das ist was als Anschauung dahintersteckt zu sagen großes O von in Quadrat – auf lange Sicht ist es so – wenn ich die Zahl – der – Elemente die sortiert werden sollen verdoppelte – dann vervierfacht – sich – diese Dauer – das ist damit gemeint – diese Zahl verzehnfachen – ?? Elemente die sortiert werden sollen dann vor hundert achtzig – die Laufzeit – Pi mal Daumen das passt umso besser je größer diese Sen wird ein methodisches Verhalten soll umso besser passende Größe des NB ich gucke mir nicht die klein N anerkannt und das was sie sehen – wenn – ein gleich einziges Tuch bekommt ?? null raus wenngleich einfarbig null vergleiche – an die Kleinen interessieren mich nicht mich interessiert was das Verhalten ist ein N über alle Grenzen wächst das Asymptote schon Verhalten – gleich noch was zu sagen das es eigentlich nicht so praxisnah je mehr man sich das anguckt aber das ist die Idee der theoretischen Informatik die Beschreibung solcher Algorithmen – das anekdotische – Verhalten für immer mehr immer mehr – Elemente dich rein geben in diesem Fall – ist es die Größe der Liste die Länge der Liste dich sortieren will – wovon – in Quadrat würde man sagen dass der führende Term ist – an – mathematischer – seits – in ?? wird man nicht so rum ich – gebe Norman Bar – Aufgaben – ?? fange erst mal – induktiv – an wie funktioniert dieses groß Eurosymbol – an – gucken uns mal sie gucken sich mal folgendes an ich hab schon gesagt es ist Buffon in Quadrate – Frage ist es auch folgendes – nämlich ist es wovon eins – ist es – of von – Wurzel in – ist es O von – N – O von N – Logarithmus – N mal Logarithmus aus ähm – ist es wovon – ein hoch drei – ist es Hof von – zwei hoch ähm – Komma lieber so an bevor ich noch mal offiziell sagen wie den einst das definierte Spitzen groß O – aus dem Bauch heraus habe ich also eine Funktion – die Anlaufzeit – abstrakte Weise ist die Anzahl dann vergleiche jetzt die Anlaufzeit – dieses sie benötigt für eine Eingabe groß von ähm – das nennen wir O von in Quadrat Asymptote Schwenn in über alle Grenzen wächst verhält sich dieser Ausdruck Asymptote Tisch – wie ein Quadrat – was wird jetzt aus dem Bauch aus meinen dieser selbe Ausdruck hier in mal N minus eins Halbe ist das auch wovon eins und so weiter – von welcher Ordnung – ist der – von denen sechs ?? unten was kann ich noch alles ankreuzen als Richt ✂ ich muss also noch bisschen mehr zu Intuition sagen – die Schreibbüro von irgendwas – meine ich – alle Funktionen – die höchstens so schlimm wachsen wie ein Quadrat – was ist der Gedanke bei dem groß – O – von der Ordnung im Quadrat es wächst höchstens so schlimm gotisch – wächst es höchstens so schlimm wie ein Quadrat – und jetzt vom Gefühl her diese sechs – verschiedenen Oster unten – das ist – mein Wachstum – der Funktion einmal in Minerals habe das es meine Funktion – möchte Wissen – wächst die höchstens so schlimm wie – eins Wurzel N – N und so weiter – sollte aus dem Bauch heraus gehen ✂ ?? die Funktion die in den Klammern vom O steht die soll schlimmer – sein oder genauso schlimm sein im Wachstum – wie meine – Funktion nicht einordnen – werde ?? das ist der Punkt ✂ also – allein aus dem Bauch heraus mit Wissen angewöhnt hat – das hier geht methodisch wie ein Quadrat – eins – ist – doch gar nicht am wachsen – wovon eins schreibt man immer für – Funktionen – Zeit Komplexität mit einer Sachen für Funktionen die – effektiv gar nicht wachsen wovon eins oder O von zwoundvierzig – oder Wasser Klammer auf von einzelnen heiligsten – an diese Funktion hier oben ist definitiv nicht wovon eins – N Quadrat wächst definitiv schneller als eins – wovon eins Gemüse nicht nennen – O von Wurzlen können sie auch nicht nennen weil im Vertrag schneller wächst als Wurzel in – den Fahrradweg schneller als in Komma sie auch nicht nennen entweder wächst auch schneller als ein Logarithmus änderten sich ?? Komma vorführen – was haben sie auch an aus dem Bauch eben schon richtig gesagt und – sonst auch – das würde funktionieren – diese Funktion hier ist – wovon in hoch drei – und sie ist wovon – zwei hoch in – ein Quadrat wächst langsamer als in hoch drei im Quadrat wächst langsamer – als zwei Wochen ähm aus man könnte auch hier schreiben diese Funktion mir die Anzahl der Vergleiche – ist – Buffon in hoch drei und sie ist wovon – zwei hoch – die – Funktion die ich hier angeben bei dem groß O – die muss mindestens so schnell wachsen – wie die Funktion – von der ich wissen will – schnell selbst dann geht das mit dem groß O – so – der Sommer die offizielle Definition – am – ?? gucke mir das Verhältnis – an – ich sage – eine Funktion F – ist – wovon – geh – ich ?? das ingenieurmäßigen – Sage eine Funktion F von N ist gleich – O von – G von N – in der Form F – Funktion wieder eben einmal – in minus einshalber und geh von ähm mir sowas wie ein Quadrat oder ändere – in – das – wenn – folgendes – gilt – dass das Verhältnis – von den beiden – beschränkt bleibt wenn das immer kleiner ist eine als Anzahl ?? gern in Betrag strichen Java keine negativen – zeitdauerndes – Risiko mich aber gerne dein Betrag schlich mich das hinkriege dieses Verhältnis ist immer kleiner als eine Zahl ähm – für alle – en – und dieses ähm ist eine feste Zahl eine feste endliche Zahl – das möglich ist – dann sage ich – das die Funktion F – von der Ordnung die von NS das ist ingenieurmäßige – Schreibweise – mathematische – Schreibweise sieht haarsträubend aus – aber ist viel logischer man sich – hinein denkt – F ist Elements – groß O – von G – das wäre die mathematische Schreibweise – groß O ist für die Mathematikerin – und Mathematiker eine Menge von Funktionen mit bestimmten Wachstum alle Funktionen – die maximal – Asymptote so schnell wachsen wie die – eine Menge und dann sage ich F ist Element der Menge – alle Funktion die maximal so schnell wachsen Asymptote Spiegel – einig müssen auch immer noch an ?? geben – ähm was den geführten Grenzwert gerade gemeint ist hier bei den NS klein N gegen unendlich – da muss ich nicht angeben – und wenn sich das angucken – über die noch mal war das – da was nicht ganz offensichtlich – wenn sie den hier einsetzen – ich möchte wissen ob – ein Quadrat – ob ein Quadrat oder wie vom ?? von oben egal ob ein Quadrat durch N mal den Logarithmus von N – beschränkt bleibt – kann ich kürzen – und CN durch Druckrhythmus von N sollten sich aus dem ersten Semester inneren Entwicklung muss von innen bleibt nicht beschränkt N wächst schneller – als der Logarithmus – deshalb – ist meine Funktion im Quadrat nicht in O von Anneken – an das in dieser Asymptote Betrachtung – die schreibt man typischerweise – dann für solche Algorithmen hin – diese Algorithmus – Sessions Ort hat eine Laufzeit – von O von N Quadrat – der Ordnung ein Quadrat – an – Quicksort – hat typischerweise – eine Laufzeit – von – einen Logarithmus – ähm – typischerweise – im Mittel – aber leider kann man Pech haben worst case – im schlimmsten Fall hat Quicksort auch – diese Laufzeiten – an das einzige sehen wenn ich minder sortierten Liste rein gehe in meine Simpl Implementierung – dann braucht er leider bisschen länger – bei vier Verfahrens die mittlere Laufzeit verschieden von der schlimmsten Laufzeit worst case – insbesondere – Quicksort dass es worst case für Quicksort und das ist der – Mittelwert die mittlere Laufzeit für Quicksort – und das ist deutlich effizienter – als – solcherart – und Bubblesort – abschließende – Bemerkung dazu ?? – man darf diese O von sonst was nicht zu ernst nehmen im Rahmen neben – man – kann – einen – einen Algorithmus bauen mit – Armen – mit – Laufzeit mit expliziter Laufzeit – zum Beispiel – aus aber jetzt mal einfach – ich kann den Algorithmus haben mit exponentiell Laufzeit sowas wie die hoch ein oder zwei Wochen Komma ganze Zahlen sowas wie zwei ?? ein ein richtig Langsamer Algorithmus – wenn ich – zehn Elemente rein gebe – braucht der ?? Faktor tausend vierundzwanzig – wenn ich elf Elemente ein gewisser Faktor zwei länger – für jedes Element was ich rein gebe mehr rein geben wird um Faktor zwei länger ein richtig Langsamer Algorithmus – Ruf von zwei hoch ähm – es kann aber sein das wovon zwei auch in trotzdem – in der Praxis – in den wöchentlichen ?? zusammenhängt dass der trotzdem in der Praxis – schneller – ist als irgendwas was Moreau von N ist stellen sich vor sie haben hier – zehn hoch hundert – Klos – N – als Laufzeit – ein Algorithmus – der erst mal das Universum sortiert sozusagen und dann kümmerte sich – um ihr Problem – dar würde ich sagen des of von N – hier das Verhältnis bilden dieses durch ähm was passiert wenn in über alle Grenzen wächst – dann – endlich – das wäre ein Algorithmus O von N – und das wäre eine Algorithmus O von zwei Wochen – absurderweise – ist dieser Algorithmus hier – für die meisten praktischen Fälle – langsamer – als der Grund muss der – eigentlich langsame aussieht von Demo von Annas man darf diese of – diese O Angaben nicht überbewerten – sind immer symbolisch Angaben – wer ist im unendlichen schneller – aber das unendliche ist sehr weit weg – Punkt es kann sein das in der Praxis – der Algorithmus der – laut Handbuch langsamer aussieht ?? – der schnellere