Die O-Notation EINFACH ERKLÄRT! (Landau Notation)
Programmieren Starten
https://www.youtube.com/watch?v=NKRO2GbjaAo

Transkript (automatisch erstellt)

0:00 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
0:09 was es überhaupt bedeutet dann bleibt unbedingt dran denn in diesem video werde ich dir das erklären hallo und herzlich willkommen auf dem
0:24 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
0:34 beziehungsweise die großen rotation überhaupt bedeutet was diese darstellt und ja wie man diese entsprechend deuten kann
0:42 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
0:52 beziehungsweise die große rotation beschreibt die komplexität von algorithmen jetzt fragt man sich aber okay komplexität von algorithmen was ist
1:03 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
1:11 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
1:20 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
1:31 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
1:40 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
1:51 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
2:00 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
2:08 sondern um den benötigten speicherplatz der für die ausführung gebraucht wird die platz komplexität beschreibt also das wachstum des
2:18 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
2:28 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
2:37 algorithmen in sogenannte komplexität klassen einteilen und das zeigt uns dann eben wie komplex ein algorithmus sein kann
2:45 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
2:57 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
3:07 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
3:17 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
3:31 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
3:39 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
3:49 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
4:00 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
4:12 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
4:21 sehen wir den timon in der konsole die nächste komplexität die wir uns anschauen werden ist die komplexität klasse von n
4:31 und diese beschreibt einen linearen aufwand was bedeutet dass das bedeutet ganz einfach dass der aufwand des algorithmus linear mit der eingabe menge
4:43 steigt sprich verdoppelt sich zb die eingabe menge dann verdoppelt sich auch der aufwand diesen algorithmus durchzuführen
4:51 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
5:03 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
5:14 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
5:23 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
5:32 anzahl an elementen in diesem areal am bass und dann haben wir den durchschnittswert warum ist der aufwand hier linear
5:39 naja nehmen wir mal an wir haben hier einen double arrangers das hat zehn zahlen dann muss diese von schleife hier ja nur
5:47 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
5:58 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
6:09 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
6:21 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
6:29 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
6:40 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
6:53 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
7:06 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
7:15 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
7:24 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
7:36 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
7:44 video beschreibung finden da wird der algorithmus also nochmal genauer erklärt falls du das wissen will ist aber ganz einfach erklärt der
7:51 babbels ort algorithmus der sortiert die elemente in diesem jahr dass man hier übergibt ich habe jetzt einfach zahlen übergeben
7:58 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
8:09 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
8:19 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
8:29 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
8:41 durchlauf der äußeren vor schleife wird auch noch eine innere vor schleife durchlaufen die dann natürlich auch noch mal
8:50 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
9:01 genauer verstehen möchtest dann schauen die video beschreibung dasein link zur erklärung und ja das funktioniert jetzt eben hier
9:08 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
9:20 immer weiter nach oben schweben und die kleinen zahlen unten bleiben und irgendwann haben wir dann eben durch diese verschachtelten vor schleifen
9:28 aufrufe diese eingabe menge numbers sortiert der grund dafür warum das quadratische ist ist eben der dass wir hier diese verschachtelte vor schleife
9:37 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
9:49 diese innere vor schleife auch noch mal öfter durchlaufen müssen wir haben also nicht mit einem neuen elementen nur ein vorschlag im aufruf
9:57 mehr sondern hier zwei vor schleifen die mehr aufgerufen werden und ja entsprechend wächst der aufwand die komplexität quadratisch das ist also
10:08 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
10:18 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
10:26 nicht getan hast dann abonniere doch diesen kanal um nichts mehr zu verpassen wir bringen regelmäßig neun programme bezogenen content wie diesen hier
10:33 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
10:40 tag auf wiedersehen