Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Big O Notation/Landau-Notation in 6 Minuten | Zeitkomplexität und Platzkomplexität von Algorithmen
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 46 Zeilen
- wenn man ein algorithmus betrachtet ist eine der wesentlichen fragen wie schnell ist mein algorithmus und wie viel speicherplatz benötigt er sagen wir
- beispielsweise wir wollen eine ray der länge 10.000 sortieren und haben zwei algorithmen a und b zur auswahl braucht 01 sekunden und b 0,3 sekunden als also
- klar die bessere wahl oder naja was passiert aber wenn wir statt 10.000 eine million elemente sortieren wollen plötzlich ist deutlich schlechter als b
- und bei 10 millionen elementen verstärkt sich der effekt noch mal deutlich wir müssen also zwei fragen stellen wie wächst die rechenzeit in abhängigkeit
- von der eingabe länge das ist die frage nach der zeit komplexität und wie wächst der benötigte speicher mit der eingabe länge die frage
- nach der platz komplexität und um diese unterschiedlichen verhaltensweisen von algorithmen zu klassifizieren gibt es die piccolo taschen oder auch anbau
- notation formal sagt man dass eine funktion fnn in der ordnung von ge von andy genau dann wenn eine zahl m größer null und ein ende lexis tieren so dass
- für alle m größer gleich null gilt dass der betrag von fr ein kleiner gleich g von m x unserer zahl m ist schauen wir uns beispielsweise die funktion fnn ist
- gleich 60 4 -2 3% + 5 an der betrag dieser funktion ist offensichtlich kleiner gleich sechs er noch vier plus zwei hoch 3 + m + 5 und
- dies wiederum ist kleiner gleich sechs er noch vier plus 2 84 prozent auf 4 + 5 m hoch vier für größer gleich eins was dann insgesamt 14 04 ist das heißt wir
- haben hier unser m gefunden unser g von n und unser 1 0 für das eben gilt dass der betrag von fnn kleiner gleich mg von
- ennis und damit wissen wir dass fm in der ordnung von n hoch vier liegt für entgegen unendlich wir betrachten wir also wie verhält sich die funktion für
- große n bzw entgegen unendlich und aus der definition können wir zwei einfache regeln ableiten nämlich erstens können wir konstante vor faktoren ignorieren so
- ist 14 m hoch vier natürlich in ordnung von einem hoch 4 und 32 mal der logarithmen ist von der ordnung logarithmisch von n
- und zweitens ist nur der dominierende team relevant für die ordnung bei 3 1 quartal + 4 m + 1 überwiegt der quadratische term und bei zwei hoch
- +44 das logo rhytmus dann überwiegt zwei hoch das heißt wir haben hier eine exponentielle ordnung und hier ist eine tabelle welche ordnung welche dominiert
- ganz am anfang haben wir eben die konstante ordnung die wird von allen dominiert dann der logarithmisch von and linear quadratisch kolonial und
- exponentiell wie bekommt man jetzt die laufzeit komplexität von algorithmen heraus nein wir betrachten einfach mal dieses
- beispiel wir haben hier eine ray der länge m range erzeugt einfach eine rey mit den werten null bis minus 1 und wir berechnen iks einfach durch bereits
- vorgegebene elemente dieses arrays mit einer einfachen rechnung und man sieht hier dass die berechnung von iks überhaupt nicht von ihm abhängt das
- heißt wir haben eine konstante anzahl von rechenoperationen also konstante laufzeit und befinden uns damit in der ordnung rufen 1 wenn wir jetzt über das
- array der länge integrieren und jedes mal eine operation der ordnung 1 ausführen wie es die formation eben ist dann führen wir insgesamt in operationen
- aus und es handelt sich damit um ordnung von n und das würde sich auch nicht ändern wenn wir mehrere operationen der ordnung
- 1 also zum beispiel mehrere addition in der schleife machen denn das würde nur einen konstanten vor faktor bedeuten der ja wieder wegfällt und auch wenn wir
- unsere schleife in eine weitere schleife konstanter länge packen ändert sich nur der faktor denn wir führen die schleife dann eben in diesem fall vier mal statt
- einmal aus dh wir haben wir auch wieder nur ein konstanter faktor und wir sind dann wieder in der ordnung von n wenn wir allerdings eine schleife die
- über das ray der länge integriert in eine schleife die ebenfalls über das array der länge integriert packen dann führen wir ja ma lin operationen aus das
- heißt sie sind in der eingabe länge quadratisch und damit in der ordnung von oven quadrat und wie schon erwähnt ist nur der dominierende term
- ausschlaggebend in diesem programm haben wir beispielsweise verschiedene teile die die ordnungen 1n und ein quadrat haben und bei großen überwiegt natürlich
- wieder der quadratische teil dh dieses programm hat insgesamt ordnung ein quadrat viele algorithmen haben natürlich mehr als eine eingabe wir
- haben hier beispielsweise zwei race der längen nbz wm und zwei verschachtelte schleifen die über das erste bzw zweite reparieren und die laufzeit komplexität
- hängt damit sowohl von innen als auch von m ab wir haben hier marleen operationen und damit die ordnung einmal m
- bezüglich der platz komplexität ist es so dass wenn wir keinen weiteren speicherplatz benötigen wir eine platz komplexität der ordnung 1 haben wenn wir
- die eingabe probieren haben wir eine von n und ansonsten hängt sehr stark davon ab welche datenstruktur nicht verwende und wie ich die verbände
- außerdem wichtig ist es zwischen barca und average case zu unterscheiden häufig ist nur der worst case angegeben der worst case beschreibt die maximale
- laufzeit bzw den maximalen speicher bedarf des algorithmus bei der schlechtmöglichste eingabe der best case eben die minimale laufzeit und der wtcc
- es die erwartete durchschnittliche laufzeit bei bekannter verteilung der eingaben wenn man beispielsweise eine liste aus einnahmen von vorne nach
- hinten linear nach einem bestimmten haben durchsucht dann wäre der worst case dass der name ganz hinten ist wie also elemente durchsuchen müssen der
- best case wert dass er ganz vorne steht wie als eine laufzeit von 1 haben und der white case ist dass der name in der mitte zu finden ist was auch wieder eine
- laufzeit von oven bedeuten würde hier nochmal ein graf der verschiedenen wachstums verhalten und daran sieht man ganz gut wie krass einige algorithmen in
- der eingabe länge explodieren können und weil man hier von 10 von loga rhytmus dann endlich ganz unterscheiden kann habe ich noch mal ran gezoomt so sieht
- es dann etwas rein gesund aus noch zwei hinweise für die praxis konstante vor faktoren sind natürlich wichtig es macht natürlich ein unterschied ob ich eine
- laufzeit von 1000 n oder cnh und best case und average case in ebenfalls der relevant wie gesagt häufig wird meistens so der worst case angegeben aber es ist
- natürlich in der praxis besonders relevant das war es auch schon wieder vielen dank fürs zuschauen über ein like oder abo würde ich nicht
- freuen außerdem könne mich über paypal unterstützen den link dazu findet in der video beschreibung bis zum nächsten mal
- [Musik]
Zum Nachlesen
KomplexitätKomplexe Ordnungen sind ständig im Wandel. Die Zunahme von Komplexität wird als „positive“, die Abnahme als „negative“ Komplexifikation bezeichnet. [A 9].
ZeitkomplexitätUnter der Zeitkomplexität wird in der Informatik die Anzahl der ... Bubblesort zwar für große Datenmengen ein recht langsames Verfahren, eignet …
InformatikAls einfache Rechengeräte leisteten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruierte Blaise Pascal eine mechanische …