Big O Notation/Landau-Notation in 6 Minuten | Zeitkomplexität und Platzkomplexität von Algorithmen
Turing Informatik
https://www.youtube.com/watch?v=x9NhQUxyCpY

Transkript (automatisch erstellt)

0:00 wenn man ein algorithmus betrachtet ist eine der wesentlichen fragen wie schnell ist mein algorithmus und wie viel speicherplatz benötigt er sagen wir
0:07 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
0:17 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
0:26 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
0:33 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
0:40 nach der platz komplexität und um diese unterschiedlichen verhaltensweisen von algorithmen zu klassifizieren gibt es die piccolo taschen oder auch anbau
0:47 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
0:58 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
1:08 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
1:18 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
1:29 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
1:37 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
1:46 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
1:56 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
2:03 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
2:13 +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
2:23 ganz am anfang haben wir eben die konstante ordnung die wird von allen dominiert dann der logarithmisch von and linear quadratisch kolonial und
2:31 exponentiell wie bekommt man jetzt die laufzeit komplexität von algorithmen heraus nein wir betrachten einfach mal dieses
2:37 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
2:46 vorgegebene elemente dieses arrays mit einer einfachen rechnung und man sieht hier dass die berechnung von iks überhaupt nicht von ihm abhängt das
2:53 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
3:02 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
3:10 aus und es handelt sich damit um ordnung von n und das würde sich auch nicht ändern wenn wir mehrere operationen der ordnung
3:17 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
3:24 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
3:32 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
3:40 ü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
3:48 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
3:56 ausschlaggebend in diesem programm haben wir beispielsweise verschiedene teile die die ordnungen 1n und ein quadrat haben und bei großen überwiegt natürlich
4:04 wieder der quadratische teil dh dieses programm hat insgesamt ordnung ein quadrat viele algorithmen haben natürlich mehr als eine eingabe wir
4:13 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
4:23 hängt damit sowohl von innen als auch von m ab wir haben hier marleen operationen und damit die ordnung einmal m
4:30 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
4:37 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
4:45 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
4:53 laufzeit bzw den maximalen speicher bedarf des algorithmus bei der schlechtmöglichste eingabe der best case eben die minimale laufzeit und der wtcc
5:02 es die erwartete durchschnittliche laufzeit bei bekannter verteilung der eingaben wenn man beispielsweise eine liste aus einnahmen von vorne nach
5:09 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
5:16 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
5:24 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
5:32 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
5:40 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
5:48 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
5:58 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
6:04 freuen außerdem könne mich über paypal unterstützen den link dazu findet in der video beschreibung bis zum nächsten mal
6:11 [Musik]