Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Die O-Notation EINFACH ERKLÄRT! (Landau Notation)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 66 Zeilen
- wenn es um algorithmen geht dann wird man sehr häufig mit dieser notation hier konfrontiert wenn du schon immer wissen wolltest was es damit auf sich hat und
- was es überhaupt bedeutet dann bleibt unbedingt dran denn in diesem video werde ich dir das erklären hallo und herzlich willkommen auf dem
- youtube-kanal von programmieren - starten punkt.de mein name ist jannik grün und in diesem video möchte ich dir mal erklären was die landauer notation
- beziehungsweise die großen rotation überhaupt bedeutet was diese darstellt und ja wie man diese entsprechend deuten kann
- fangen wir dabei an mit einer ganz ganz einfache erklärung dafür was diese notation überhaupt beschreibt und das ist ganz einfach die landauer notation
- beziehungsweise die große rotation beschreibt die komplexität von algorithmen jetzt fragt man sich aber okay komplexität von algorithmen was ist
- das überhaupt und es gibt tatsächlich verschiedene arten von komplexität die man hier beschreiben könnte mit der landauer notation und zwar gibt es da
- einmal die zeit komplexität und die platz komplexität und diese beiden gucken wir uns jetzt mal an fangen wir an mit der zeit komplexität
- mit zeit komplexität ist ganz einfach die aufführungsdauer eines algorithmus in abhängigkeit zur eingabe menge gemeint die zeit komplexität zeigt einem
- also wie stark die ausführungszeit wächst wenn man mehr daten in den algorithmus ein gibt also wenn die eingabe menge größer wird man sieht an
- der zeit komplexität also das wachstum der ausführungszeit in relation zum wachstum der eingabe menge sprich je mehr daten wir in einen algorithmus
- eingeben desto länger braucht dieser natürlich die daten zu verarbeiten und entsprechend wächst mit mehr daten natürlich auch die ausführungszeit und
- dann gibt es ja auch noch die platz komplexität und da ist es ähnlich wie bei derzeit komplexität nur das ist hier jetzt nicht um die ausführungszeit geht
- sondern um den benötigten speicherplatz der für die ausführung gebraucht wird die platz komplexität beschreibt also das wachstum des
- speicherplatzbedarf in relation zum wachstum der eingabe menge wir wissen jetzt also was die komplexität von einem algorithmus ist aber wofür braucht man
- hier jetzt die landauer notation bzw die großen notation wie sie auch oft genannt wird naja mit der großen rotation können wir
- algorithmen in sogenannte komplexität klassen einteilen und das zeigt uns dann eben wie komplex ein algorithmus sein kann
- hier siehst du mal die wohl einfachste komplexität klasse von 11 bedeutet dass der aufwand bei der ausführung eines algorithmus konstant ist sprich der
- aufwand verändert sich nicht mit mehr daten die man ein gibt es dauert immer gleich lange den algorithmus auszuführen und man braucht immer dieselbe anzahl an
- speicher um den algorithmus auszuführen hier wächst also der aufwand nicht egal wie viele daten man in den algorithmus ein gibt ein gutes beispiel für einen
- algorithmus bei dem die zeit komplexität von einst ist ist das lesen eines array indizes egal wie groß das array ist wenn wir einen bestimmten index ansprechen
- wollen um diesen zu lesen dann dauert das immer gleich lang völlig unabhängig davon ob in diesem areal jetzt eine million werte drin stehen
- oder nur 5 ich habe hier zum beispiel das rain ames das ist ein string array bestehen ein paar namen drin und hier habe ich eine variable vom typ string
- die heißt mein name und da schreibe ich jetzt einfach den namen mit dem index 2 hier rein aus diesem games und das ist ja hier dann der timon und den lasse ich
- dann einfach in der konsole ausgeben diese operation hier hat eine zeit komplexität von von 1 denn wie bereits gesagt egal wie viele indizes wir hier
- drinnen haben in diesem ich geb dir hier einen index an und das dauert immer gleich lang diesen dann auch zu lesen und wenn wir das dann ausführen dann
- sehen wir den timon in der konsole die nächste komplexität die wir uns anschauen werden ist die komplexität klasse von n
- und diese beschreibt einen linearen aufwand was bedeutet dass das bedeutet ganz einfach dass der aufwand des algorithmus linear mit der eingabe menge
- steigt sprich verdoppelt sich zb die eingabe menge dann verdoppelt sich auch der aufwand diesen algorithmus durchzuführen
- hier sehen wir mal ein beispiel für einen algorithmus mit linearer zeit komplexität also einer zeit komplexität von n wir haben hier einen average
- algorithmus also eine methode namens average die eben den durchschnittswert von den zahlen in diesem double rehn am bass ausgibt wie machen wir das ja ja
- wir haben ja einfach eine summe die setzen wir anfangs oft 0 und dann addieren wir auf diese summe einfach jede zahl drauf die sich in diesem areal
- am bass befindet wir durchlaufen also jede zahl in numbers und addieren diese auf die summe und am ende return wir einfach die summe geteilt durch die
- anzahl an elementen in diesem areal am bass und dann haben wir den durchschnittswert warum ist der aufwand hier linear
- naja nehmen wir mal an wir haben hier einen double arrangers das hat zehn zahlen dann muss diese von schleife hier ja nur
- zehn zahlen durchlaufen und entsprechend zehn mal hier diese summe erhöhen mit den entsprechenden numbers hier jeweils immer wenn wir jetzt sagen wir haben
- hier 15 am bass dann muss das hier eben fünfmal mehr durchlaufen werden wir haben also dann nicht nur zehn durchläufe sondern 15
- und so steigt eben der aufwand linear mit der anzahl an elementen die wir hier übergeben also mit der anzahl an zahlen indem er in numbers dass wir hier als
- parameter übergeben und deswegen ist der aufwand hier linear wenn wir also hier mal gucken wir haben hier ein double r in numbers das hat
- hier fünf zahlen und ja dann geben wir in der konsole einfach den average von diesen zahlen aus dann sehen wir haben wir jetzt hier die zahl 56,8
- der konsole stehen zu guter letzt möchte ich noch die komplexität klasse o von ewa draht vorstellen bei der komplexität klasse o von n quadrat wächst der
- aufwand quadratisch zur eingabe menge der aufwand des algorithmus entspricht also der eingabe menge an hoch zwei eine komplexität von n quadrat haben wir vor
- allem dann wenn wir zwei vernichtete vor schleifen haben also wenn wir eine äußere vor schleife haben in der sich dann auch noch eine weitere vor schleife
- befindet und würde noch eine vor schleife in die zweite reihe kommt dann hätten wir sogar eine komplexität von n hoch drei hier siehst du mal ein
- beispiel für einen algorithmus der eine komplexität von o von n quadrat hat und zwar ein ganz klassisches beispiel den babbels ort algorithmus eine sache
- gleich mal vorweg ich werde diesen algorithmus hier jetzt nicht im detail erklären dazu habe ich nämlich schon mal ein video gemacht das kannst du in der
- video beschreibung finden da wird der algorithmus also nochmal genauer erklärt falls du das wissen will ist aber ganz einfach erklärt der
- babbels ort algorithmus der sortiert die elemente in diesem jahr dass man hier übergibt ich habe jetzt einfach zahlen übergeben
- und ja die werden dann aufsteigend sortiert ich habe hier also mal ein beispiel eine beispiel eingabe menge das sind die zahlen 25 55 17 87 und 100 und
- dann sortiere ich die mit dem aufruf von bubbles ort und wenn wir das ganze dann ausgeben lassen dann sehen wir sind die hier nach der größe aufsteigend sortiert
- und der grund warum dieser algorithmus quadratische komplexität hat ist eigentlich ganz einfach ich habe es ja gerade eben schon auf der präsentation
- erklärt wir haben hier einmal eine äußere vor schleife die durchlaufen wird und zwar so oft wie wir hier elemente in dem eray haben - 1 und bei jedem
- durchlauf der äußeren vor schleife wird auch noch eine innere vor schleife durchlaufen die dann natürlich auch noch mal
- viele male durchläuft und zwar so oft wie wir eben hier j kleiner haben als numbers - 1 + ii wie gesagt wenn du diesen algorithmus
- genauer verstehen möchtest dann schauen die video beschreibung dasein link zur erklärung und ja das funktioniert jetzt eben hier
- so dass die zahlen von diesem jahr von diesem rain am bass schritt für schritt nach oben gebracht werden in der zahlenreihe so dass die großen zahlen
- immer weiter nach oben schweben und die kleinen zahlen unten bleiben und irgendwann haben wir dann eben durch diese verschachtelten vor schleifen
- aufrufe diese eingabe menge numbers sortiert der grund dafür warum das quadratische ist ist eben der dass wir hier diese verschachtelte vor schleife
- noch haben weil wir ja für jedes element das dazu kommt diese äußere vor schleife noch einmal mehr aufrufen und entsprechend für dieses eine element
- diese innere vor schleife auch noch mal öfter durchlaufen müssen wir haben also nicht mit einem neuen elementen nur ein vorschlag im aufruf
- mehr sondern hier zwei vor schleifen die mehr aufgerufen werden und ja entsprechend wächst der aufwand die komplexität quadratisch das ist also
- die komplexität klasse von m ² und das sind die komplexität klassen die ich dir jetzt für diese einfache erklärung der landauer notation einfach mal vorstellen
- wollte wenn dir das video gefallen hat würde ich mich sehr darüber freuen wenn du dem video einen daumen nach oben da lassen würde ist und falls du es noch
- nicht getan hast dann abonniere doch diesen kanal um nichts mehr zu verpassen wir bringen regelmäßig neun programme bezogenen content wie diesen hier
- und wenn das genau dein ding ist dann lass doch auf jeden fall ein abo da in diesem sinne verabschiede ich mich und wünschte jetzt noch einen wunderschönen
- tag auf wiedersehen
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 …