[Playlisten] [Impressum und Datenschutzerklärung]

12.02.1 Bubblesort, Quicksort, Laufzeit

CC-BY-NC-SA 3.0

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

Anklickbares Transkript:

ich – wollte ein paar Begriffe – erklären aus der Ecke Algorithmen – ihr zwei auf einmal suchen und sortieren – Suchen und Sortieren – und Laufzeit – ganze – Palette an Algorithmen – befasst sich damit – Daten zu suchen – ?? Datensätze zu suchen – und Datensätze zu sortieren – an – einen von der Sorte hatten das schon – Bubblesort – das ist das was man immer als – abschreckendes Beispiel für sortieren anführt Bubblesort – bekam im Seminar vor – bevor der vom Bubblesort ist – wirklich einfach zu programmieren – und er braucht – minimal Speicherplatz zusätzlich zu den nackten Daten – der Nachteil ist läuft eben sehr lange – wenn man viele Daten rein steckt – okay wie funktioniert Bubblesort – Komma – nicht abstrakt sondern am Beispiel mal erzählt – angenommen ich habe diese fünf Zahlen dreizehn fünfzehn – achtundzwanzig – drei siebenundvierzig – die möchte ich sortieren nach ?? möchte man natürlich nicht nur Zahlen sortieren man möchte irgendwelche Datensätze nach dem Alphabet sortieren – möchte Trefferlisten – nach den bestmöglichen – Sortieren – haben – Dialoge – nach Preisen sortieren und so weiter und so fort aber du stimmst es erst man sich an ?? Distanz einzunehmen und die zusätzliche man das sortieren kann – wenn es auch klappen andere Sachen sortieren – die Idee hinter Bubblesort – ist das die großen – Zahlen – aufsteigen – wie – sie vor Blasen Wasser ?? sein – Beistrich das macht wie Blasen im Wasser steigen die großen Zahlen auf das ist der Gedanke – des – Bubblesort – unten an – das ist die Ausgangslage – Ausgangslage – ich fange unten an und gucke nach – müsste die unterste Zahl aufsteigen – dass sie zu aus die siebenundvierzig – ist größer als die drei – sieben vierzig müsste Auster aufsteigen – ich tausche die beiden aus einem siebenundvierzig – der Rest bleibt erst mal so wie er war – in diesem vierzig ist schon diese Blase sieben fertig ist das hoch gestiegen – damit habe ich die untersten beiden verglichen jetzt guck ich die nächsten beiden an sieben vierzig achtundzwanzig – Optimus sieben vierzig muss noch weiter aufsteigen – ?? – die beiden tausche ich aus – Austausches – immer sehr schön was kostet – er – nur einen Speicherplatz eine Speicherstelle zusätzlich – in die sie – ein Zwischenergebnis speichern müssen ?? tausend sieben – war nichts mit aufschreiben – wie tauschen sie sieben vierzehn achten zwanzig aus diese beiden Inhalte – der beiden Speicher stellen die Bauch noch eine extra Speicherstelle – schmeißen die achtundzwanzig reine Chemie sind dem vierzig Angestellte achtundzwanzig – die achten zwanzig Dienstag gemerkt haben an die Stelle der sieben vierzig – um zwei Zahlen – um zwei Objekte auszutauschen – Komma eine extra Speicherstelle – und sonst nichts – deshalb – ist das schöne als Folge von Vertauschung und das relativ sparsam achtundzwanzigsten – vierzig – die sie wird sie bereits weiter aufsteigt sie sehen – auch – wir sind noch nicht fertig damit – die ersten beiden ?? verglichen die nächsten beiden es vergleichen diese beiden – die muss ich anscheinend auch noch austauschen – sind wir die steigt noch höher – zwanzig drei dreizehn – und – zur Krönung findet die beiden letzten Vergleiche – auch normal fünfzehn – zwanzig drei – ?? – das wäre der erste Durchgang – den Bubblesort macht – er fängt unten einen Vergleich die untersten beiden – sind in der falschen Reihenfolge den Tausch der Austernvergleich – für die nächsten beiden sind in der Freischaltreihenfolge – der Staus – die nächsten beiden sind in der falschen Reihenfolge – aus und so weiter und so fort es wäre ein Durchgang – wo sie in ein Durchgang reicht nicht – hier ist immer noch was faul beachten zwanzig Lieder Schrägstrich man muss leider mehrere Durchgänge haben also mach ich ein zweiten Durchgang – ganz – dein Geschmack sein – und – mache ein zweiten Durchgang ?? ich fange wieder unten an drei achtundzwanzigste – das sieht ja ordentlich aus dieser sich so steht – der zwanzigste größere Kreis der kleine – und dann guck ich mir an – lies dir bitte nächsten Stil achten zwanzig fünfzehn das ist durfte ich den Falschrum fünfzehn achtundzwanzig die beiden sich aus der – ?? sind diese beiden dran achtundzwanzig dreizehn – wieder falsch rum die beiden sich aus dreizehn achtundzwanzig – vierzig – fünfzehn drei – und – Art Wichtiges richtig – damit ist der zweite Durchgang beendet – und so weiter – Projekte ziehen Sie sie an – wie das weitergeht das mach ich solange bis das Ding endlich – sortiert ist – bis sich nichts mehr vertauscht habe – wenn ich von unten nach oben durchgehen kann ohne was zu vertauschen – Beistrich bin fertig das wäre die Abbruchbedingung – du kannst auch im Seminar vor – das wäre – der – simpelste – Sortieralgorithmus – die man sich so vorstellt – das abschreckende Beispiel war so fürchterlich lange braucht – wenn sie viele Zahlen haben aber es extrem einfach zu programmieren – und sehr platzsparend – was ich jetzt an zusätzlichen Daten abspeichern muss – ?? es kommt – in jedem Schritt Punkt höchstens diese eine Speicherstelle – dich noch benötige um zwei Sachen – zu kopieren – mit wirklich hart auf hart geht jeder sogar wenn's nackte Zahlen sind ohne eine zusätzlich bei der Stelle aber das ist an den Haaren herbeigezogen – typischerweise braucht man – an jeder Stelle – nur eine einzige Speicherstelle zusätzlich – unübertroffen zum – extrem Speicherplatzpan – aber etwas langsam – etwas so langsam – dass – das nächste was in der Stelle erzählen möchten Laufzeit – was ist eigentlich die Laufzeit – eines Algorithmus – wie schnell ist der in mäßig die Laufzeit – am ?? die Laufzeit des einfach stoppen sah oder sind soundsoviel Mikrosekunden – und Millisekunden wenn ich fünf – Sachen rein klatschen – was einen typischerweise – interessiert ist die Asymptote Laufzeit was passiert wenn es nicht fünf sind – Insolvenz zehn Cent was passiert wenn sich zehn Sitzungen mit zwanzig sind wie wächst die Laufzeit – mit der Zahl – der Eingaben – das ist – eine ganz übliche – Frage in der – Informatiker – wenn sie ähm Zahlen haben – sich das vor dafür gefälligen Text das et cetera so freizügig mit meinem inneren Text – ?? stellt sich vor sie müssten Kennzahlen – sortieren – nicht fünf sondern ähm – wie lange würde das Pi mal Daumendauer – wäre – eine charakteristische Eigenschaft für diesen Algorithmus – wie lange dauert das Klima dann wenn ich in Zahlen allgemeine Sen – sortieren will – Pi mal Daumen ?? – man sich das überlegen – waren – in jedem Durchgang – ?? Durchgang – wie viel Schritte haben sie pro Durchgang wenn sie Kennzahlen – sortieren – müssen – die mal Daumenchef – Mitchell Pi mal Daumen geschätzt wie viel ✂ sollte von der Größenordnung – N sein – wie vielen – Schritte hier jeder Durchgang braucht – unten Vergleichen Ines vergleichen Essen vergleichen – hieraus – ein bisschen weniger weit unten Beistrich stimmen – beim nächsten Mal wahrscheinlich noch ein bisschen weniger – aus einer von mir aus in der Mitte – im Mittel baut leicht – en halbe Schritte pro Durchgang um faustformelmäßig – mal Idee zu haben ?? pro Durchgang in halbe Schritte – beim ersten Mal natürlich wirklich alle durch von unten – bis oben und wenn ich bisschen raffinierter bin ich sich hier schon ?? die beiden waren sortiert im Sinne ganze viele machen und so weiter – es würden immer weniger werden – aber – nichtsdestotrotz – im Mittel Klammer auf wo sich ein halbes tatsächlich Hände wedeln zwar nicht um Idee zu kriegen wie schlimm es wird pro Durchgang in halbe Schritte – an wie viel Durchgänge werde ich immer dann brauchen ✂ schlimmstenfalls brauchen Sie wirklich – in Endes eins Ende zwei muss man sich überlegen offene Größenordnung – in Durchgänge – Gleichzeichen bisschen schneller – am – reicht – im Mittel gleich mit viel Glück in halbe Durchgänge – aber von der Größenordnung – ist da nicht viel besser werden ist dann auch nicht viel schlechter werden – das heißt insgesamt – insgesamt habe was wie ein Quadratmeter – Schritte – sehr grob abgeschätzt ?? Idee zu kriegen das heißt wenn sie zehnmal – soviel Daten sortieren – erwarten Sie was passiert mit der Laufzeit ✂ als ich würde erwarten wenn ich von fünf Daten die zu sortieren sind auf fünfzig gehe Faktor zehn – N vergrößert sich um den Faktor zehn für dich erwarten – dass die Laufzeit des ganzen Faktor hundert sechs – was nicht richtig gut ist – ?? sich vor sie fangen wirklich wollte ich mal Millionen Daten sortieren das wäre mit diesem Algorithmus überhaupt keine gute Idee – hätten sie das dann irgendwas von der großen und eine Million ins Quadrat – es gibt eine passende Idee – die langsam zum Algorithmus ist das ?? jetzt – wie gesagt total Handy während der Contrastunde – ansetzen sich genau überlegen wie lange das dauert und sich nicht wirklich – am – ?? im allgemeinen reicht es ohne grobe Idee zu haben – wie schlimm – das Laufzeitverhalten – von zum Algorithmus ist und sie sind dieser Algorithmus – scheint irgendwas mit N Quadrat zu produzieren was man dann angeht – was man dann angibt – sieht so aus wovon im Vertrag – zu – diversen Texten abschreiben – ?? man schreibt hin – ?? Asymptote – Asymptote Laufzeit – Asymptote – schon Laufzeit – ist – groß wovon ein Quadrat so schreibt man das dann in – die Laufzeit – für große ähm Asymptote die Laufzeit für groß N – wird etwas sein – das – durch eine Konstante mal ein Quadrat – beschränkt wird – also wenn die Laufzeit wenn die exakte Laufzeit sowas wäre wie – sagen wir zweiundvierzig – mal in Quadrat – plus sieben Mal endlos – acht – wenn das die echte Laufzeit wäre – die Zahl der Rechenschritte – dann wäre das wovon in Vertrages – wird beschränkt – durch ein – Vielfaches – von ihm vertrat ein handfestes Vielfaches von dem Quadrat für große N – es wächst wie ein Quadrat im Endeffekt so gibt man das dann ohne von ?? Quadrat – das schreibt man das typisch war sie dann so die Handbücher sozusagen zu den Algorithmen – was ist die Laufseite finden Sie solche Ausdrücke dieses groß O – nennt sich das Landau groß O – im ersten Semester in der Mathematik – kann gerade was vor über das Landau klein O – beim ableiten dass das Landau groß O – groß neunzehn ?? groß O – groß O – eine Zahl in der Größenordnung – von in Quadrat – ist unschön und es unpraktisch ist immer das hin schreibt weiß man nicht ob zweiundvierzig in Quadrat sind oder zehn hoch fünfzehn – N Quadrat – all das wäre immer noch – Ordnung von den Quadrat insofern ist diese Analyse nicht gerade sehr praktisch – Punkt es gibt an ein erste Idee über das Wachstumsverhalten – von der – Laufzeit – viel schlimmer noch – was wäre noch viel übler als O von den für was wäre noch offenen Quadratssee – aber noch übler aus als sie nur fünfzehn in Quadrat ✂ aber wenn sie sehen es ist ganz banal – ständig vor der steht normal – plus zehn hoch hundert dahinter – in ein Quadrat wenn N gegen unendlich geht ist das immer noch durch ein Vielfaches von dem Fahrrad beschränkt – aber die CN gleich eins einsetzen – monströse Laufzeit in gleich zwei monströse Laufzeit so ein Algorithmus wäre in der Praxis überhaupt nicht – nutzbar – wäre trotzdem im Sinne der Informatik – von der Laufzeit ?? und Laufzeit wovon im Quadrat – diese Analysen – eher nach – Durchlaufzeitanalyse – muss man mit – der figürlichen Salz – nehmen – am Mann kriecht eine grobe Idee wie schlimm sein Algorithmus ist dieser ist richtig schlecht ein Quadrat in der Suche sich richtig gut – aber – diese Analyse sagte nicht alles – die Faktoren dabei stehen können monströs sein – und – es können zum Beispiel solche Konstanten noch dabei stehen die man über berücksichtigt – das Verhalten – kaputt machen – aus dieser ?? Durchlaufzeit – nicht zu wichtig nehmen das ist ein erster Schritt – nicht überlegen – wie gut und wie schlecht – ein Algorithmus ist – am – ?? – aber das ist nicht der Weisheit letzter Schluss – so auf jeden Fall ist dieser Algorithmus – das kann man aber schon sieht dieser Algorithmus Bubblesort ist nicht wirklich gut in Quadrat – wenn sie die Zahl an interessierenden – Elementen – verzehnfachen – ?? hundert achtzig die Laufzeit – das sieht auf jeden Fall schon mal sehr schlecht aus und es wird dann auch wirklich sehr schlecht aus wenn ich eine Hand Vollsachen zu sortieren habe – ich hab sehr wenig Speicherplatz – und diese Zeit dann mach ich Bubblesort Roller gut funktioniert – und einfach so offen Kopf hinschreiben kann – am – wenn es ernsthaft einsortieren geht ist das Schlechte Idee – es gibt – tausend eine Möglichkeit – aus einer Gruppen der Fall bei tausend ein Algorithmus dafür ?? ich will ein Zeichen – der netterweise auch in C eingebaut ist Quicksort – den – Pinsel in der Standard sei widersinnig drin – steht in mehr Details in seiner Lipp Punkt H – wenn sie gut jussorgt – Quicksort der ist eingebaut ?? – ganz leicht zu bedienen am simsen bisschen – solche Sachen an wenn wir das im Praktikum hatten korrekt Funktionen solche Geschichten – am – Prinzip Quicksort tatsächlich eingebaut der ist typischerweise – schneller – als ?? zur – üblicherweise lassen sich da noch sagen Punkt typischerweise eigentlich nur – Komma dass es kein Ding das man also gerade aus dem Stehgreif – zu Fuß programmiert – am Beispiel mal meine Ausgangslage – so aussieht diese Zahlen habe ich – sieben Stück – sechzig – dreizehn – zweiundvierzig – sechsundfünfzig – sieben acht – sieben acht zwölf – besser meine Ausgangslage – sein – die möchte ich sortieren – und nehme nun etwas intelligenter als mit Bubblesort – am – Quicksort tut folgendes – erblickt sich ein Element als – Gewürz – Pivot – Dreh und Angelpunkt raus welches auch immer ich bin mir durch die Salzwand vierzig aus müsse sich geschickt dann überlegen welche man rausbekommen – könnte ?? zufällig einen nehmen könnte die ersten in die letzte nehmen wir Komma ich bin jetzt hier die ihr – Mann ernennt eine dieser Zahlen – zum – Debit Pivot – Dreh und Angelpunkt – welch – auch immer – Komma – wenn sie wolle zufälliges Erleben ganzjährig bei den bei Events bei den – Algorithmen – darf ein Algorithmus Zufallselement – enthalten – eigentlich schon könnte zum Beispiel – aus Würfeln welche dieser Zahlen – der Pivot – bewirkt sein soll – und in den den ersten in den letzten ?? mit ihrem – ich nehme ein so – was man nun macht – man zerteilt seine ursprüngliche – Liste – in zwei Listen – zahlen die kleiner sind – als der Pivot uns wird und zahlen die größer sind – als Apple wird – als ich bilde zwei Listen eine Spende ich die Zahlen kleiner – als zwei vierzig rein schmeißen dreizehn kommt herein – und die sieben kommt herein und die acht kommt da rein – einmalig Beistrich wechselt schick aus so – euch alle Mitglieds zwölf ?? auch noch – sein wir diese wo und was habe ich darüber – darüber habe ich die sechzig – und die sechsundfünfzig – aller – sieben Stücke – das – macht man im ersten Schritt – und – nun kommt der große Kunstgriff – nun nachts nun ruft dieser Algorithmus sich selber auf – hier habe ich wieder eine Liste an Zahlen – die sortiert werden soll – ?? Ruf der sich selber auf – dasselbe noch mal – das nennt sich Rekursion gleich mehr dazu – dieses – Verfahren ruft sich rekursiv selbst auf und es hat eigentlich nur diesen einen Schritt – sie neben die Liste suchen sich ein Element dass sie als Dreh und Angelpunkt – in die Mitte stellen wollen sozusagen – alle die kleiner sind als das schieben sie auf die eine Seite alle die größer sind als das schieben sie auf die andere Seite – jetzt haben sie zwei Listen – auf die sie dasselbe noch mal anwenden können – Komma sich an den eigenen Haaren aus dem Sumpf ziehen – das ist Rekursion – auf diese Liste wende jetzt das Verfahren noch mal an – in den irgend einen über die acht von mir aus hier jetzt – für diese Liste zu – ?? wird und siehe da nur Security sieben ist kleiner die acht bleibt er stehen – und dann habe ich zwölf – dreizehn – um diese Liste zu verarzten – ?? mal ich das mal sinnvoll auf – eine – Reise zur Frage – zwölf – wie man im einzelnen sortiert es sowieso noch immer die meisten und schichtet es sowieso ?? Kunst für sich aber ich hatte das immer weiter in der Reihenfolge hin so sind ?? die sieben damit bin ich erledigt – diese Liste – ist natürlich bisschen Arbeit mit dem Verfahren zu sortieren ich würde mir jetzt hier ein ?? mit Aussuchen vom erste zwölf – Ziffer dass er dich auf die beiden werden es einfach in die richtige Reihenfolge stellen zwölf dreizehn – dann ist derzeit erledigt – diesen Teil muss sie erledigen da stehen zwei – er wisse täglich zwei Zahlen das kann ich es auch ohne das Verfahren sie ständig einfach in die richtige Reihenfolge sechsundfünfzig – sechzig – und dann habe ich sieben acht zwölf dreizehn zwanzig sechsundvierzig sechzig das Ding ist datiert – das ist die Idee hinter Quicksort – als es – ein derselbe Schritt der – verschachtelt – immer wieder aufgerufen wird – man teilt die Liste in zwei Listen – zwei Teillisten – an einem ausgewählten Element und viele Detaillisten – ?? wieder in zwei Teile einem ausgewählten Element und so weiter und so fort bis man zum Schluss noch zwei Elemente hat die Kammer zu Fuß sortiert die zwei Elemente – das ist die Idee hinter – Quicksort das Ding ist eingebaut in zehn – Prinzip – ab Werk verwenden – der Brauch allerdings bisschen mehr Speicherplatz – als – der – Bubblesort – Komma hierarchische – Aufrufe hat eine Funktion – dieser Funktionsaufruf – hier bitte noch mal gemacht – dann rufe ich noch mal die Funktion auf ?? Hero die Funktion auch nochmals – die – Rücksprung – die Wertübergabe – und die Rücksprungsadressen – die Kosten Speicherplatz – und dass es auf so kleinen Gerät wie diesem SPD hundert dreißig schon bisschen Enggebrauch – auf jeden Fall mehr Speicherplatz – als – der Bubblesort – dafür läuft aber deutlich schneller – im allgemeinen muss man sagen läuft er deutlich schneller – sich jetzt hier überlegt – okay wie lange dauert das eigentlich Vincent Elemente habe – die ich sortieren will wie lange dauert das eigentlich manchmal – so glücklichen Fall in Male – Skript aus buchstabiert – müssen sich ab Mai – stellen sich vor sie haben – eine List an seine hundert achtundzwanzig – Elementen – im ersten Schritt – naja – Pi mal Daumen was ganz im erste Schritt passieren im Schnitt ?? im Schwimm Schnitt habe ich wahrscheinlich sowas wie – eine – vierundsechzig – ein Pivotelement – mit Element – und dreiundsechzig – sowas passiert bei dem ersten ?? – im ersten Schritt – dann im nächsten Schritt wird das aufgeteilt vielleicht in zweiunddreißig – ein Pivotelement – einunddreißig – und dass sie wird aufgeteilt vielleicht den einunddreißig – ein hundert zweiunddreißig – will – auch richtig mit jeweils ein dreißig sei Dank ja – Eltern die da stimmt es aber ihr müsst es eindeutig sein – und so weiter – und so fort – so könnte das gleich im Schnitt aussehen – das es auch wieder nicht streng ist der Missbrauch wieder bei Stunde investieren was streng ausrechnet – und sich nicht nur CD wie lange das dauert – lange bis zum ?? Rhythmus laufen bin ?? – en Sachen reinpacke – Komma sich überlegen – wie viel Hierarchieebenen – das hier werden – Pi mal Daumen wie viel Ebenen habe ich hier – die ✂ fortlaufende – Halbierung – mehr oder minder sowas hoffe ich zumindest dass das im Mittel passiert – es im Mittel fortlaufend halbiert wird – die oft könnte ?? zwanzig fortlaufend agieren das hat was damit zu tun ?? zweier Potenzen drin stecken zwei hoch sieben – das muss sowas sein wie der zweier Logarithmus – von den hundert achtundzwanzig – plus minus eins – bitte jetzt mal ganz grob – über den breitesten Daumen gepeilt die Zahl an Ebenen muss was mit den zwei Logarithmus der Zahl zu tun haben wie häufig kann ich – die Zahl durch zwei teilen – okay – ich will jetzt kann ich mir überlegen noch für – die Verbrechen Schritte in jeder Ebene – hat – wie viel Rechenschritte – pro Ebene – also eine Zahl wie vier – Rechenschritte pro eben ✂ von – den zweiunddreißig – wenn ich dieser Tiere in kleinen Helfer die größere Hälfte – ?? dann die Hälfte der kleineren und die Hälfte der größere – beziehungsweise – Hälfte falsch den sechzehn Fall starren die fünfzehn sechzehn falsch fünfzehn sechzehn ?? lassen sich insgesamt – vier richtig falsch ungefähr – hier – bei den vierundsechzig – wenn ich die Teile zwei Hälften zweiunddreißig – falsche Mittel – dazu eine Reise falsch da ein ?? zwei dreißig falsch – sein wie der vierundsechzig – ganz zu Beginn – werden – die mal Daumen vier sechzig Watt stark an das heißt ich werde überall vierundsechzig – falsche auf jeder Ebene vierundsechzig falsche Umsatz hier müssen – die mal Daumen – über den breiten Darm – und dann hat man eine Idee was die Laufzeit – Asymptote Laufzeit sein könnte – alles anders als strenger Beweis aber – hoffe ich eine Idee wie das zustande kommt als ähm methodische – Laufzeit – Logarithmus – von der Anzahl – rotierender Sachen – eben auf jeder Ebene – sowas wie ein halbe – Schritte im Mittel – das wäre of von – ersten Wissmann vertreiben zweier Logarithmus ein zu umschreiben – Jones versucht er eine halbe Meile zweier Logarithmus von – zwei Logarithmus von N so könnte man es erst mal schreiben – in jeder Ebene in halbe Schritte Yeti vierundsechzig – und – Lok zwei von in Ebenen – wird sich so hinschreiben – in Halbe – ist ein halbes ein konstanter Faktor – mit um das Wachstum geht – es mit S mit Nervfaktor – her egal – wie kann ich weglassen – oder das Logarithmus zwei ist oder Logarithmus zehn ist auch egal der Logarithmus zwei – ist ja der Logarithmus – zehn – von dem Ende durch den Logarithmus zwei – weitere durch den Rhythmus sind von der zwei so durch den zehn von zwei das erste Semester einer Logarithmengesetze – Logarithmen – unterscheiden sich alle nun unkonstanten Faktor – nehme irgendein Logarithmus Hauptsache seine Basis ist größer als ein Schatten auf den Basisgang – so sieht das aus das ist das übliche was sie finden für einen ordentlichen Suchalgorithmus – und es geht auch nicht besser kann sich auch überlegen ist jedoch nicht besser für Suchalgorithmus – entlockt Annas Laufzeit – will sagen – ?? wenn sie zehn Einsätzen zehn – Mal Logarithmus – zehn – wenn sie hundert Einsätzen hundert mal Logarithmus – hundert – Logarithmus hundert ist ja – zumindest – den Rhythmus von Zinsquadraten – siehe den Rhythmus ihr steht ja – ?? zehn ins Quadrat – es ist – zweimal – der Logarithmus – aus zehn – Logos aus hundert ist zweimal ?? Rhythmus aussehen – und nun sehen Sie was passiert – wenn sie ähm vergrößern – von zehn auf hundert – wird die Laufzeit – vergrößert – werden – um den Faktor – zwanzig – sind mit Zehnerlogarithmus – sondern – zwei hundert mal ?? – wenn ich das jetzt ganz dumm so rechnen – natürlich alles sehr Handy will auf jeden Fall heißt eines nicht mehr die Laufzeit – von hundertfach übers eben hatten – ein deutlich langsames Wachstum – das es was man typischerweise für Suchalgorithmen – hat – er ehrlicherweise – das hat man bei dem Quicksort nur im Mittel – wenn sie – sowas Daten rein schmeißen – tausendmal messen Mittelwert bilden dann wird das so sein – es kann einem passieren bei den Quicksort dass die Datenlöhne – liegen – das ich hier immer nur einen einzigen abspalten Beistrich Vorsicht walten in ?? bei der Halbierung – der sinnlich wirklichen Halbierung haben sondern die eine Liste ein Element und die andere als alle anderen – dann an sie aber – verdammt viele Ebenen und alles bricht zusammen im schlimmsten Fall – endlich dann worst case – die – Worst Case Laufzeit – ist leider – nicht diese hier – sondern dies wieder – ein Quadrat wie Bubblesort – aber der worst case tritt so selten ein dass man – den ?? trotzdem gerne nimmt diesen Algorithmus ✂ okay – das zu – Sortierverfahren – und Laufzeitlaufzeit – Komma die auch für andere Algorithmen angucken – aber das ist ?? das erste wo man sich das an die Sortierverfahren – Suchverfahren – sind die Schwestern der Sortierverfahren – wenn ich etwas bestimmtes suche ist das meist – gute Idee dass ich erst meine Daten sortieren – dann kann ich schneller suchen – wenn sich vor – die gucken was im Lexikon nach ?? Lexikon nicht sortiert wäre eine verdammt viel Zeit damit zu verbringen als der erste Schritt beim Suchen ist üblicherweise das Sortieren