Danke !! Ich war voll am Verzweifeln wegen des Themas aber jetzt habe ich das echt gecheckt. In 1 Woche bestätigt mir das dann mein Prof hoffentlich! :D
9:07 xD ich hatte es erwartet aber dann haste kurz ne pause gemacht und ich dachte oh er lässt es dabei und dann kahm die supper worstlaufzeit auf die ich gewartet habe und ich habe mich gefreut :,D
Tut mir leid, das bin ich komplett uebergangen. Bei Speicherkomplexitaet bin ich leider nicht ganz so sicher. Sollte aber eigentlich genauso funktionieren: - In dem Teil rechts oben (fak = new int[n]) werden n Speicherplaetze reserviert. Also O(n) - Ueber die Rekursion wird dann die Funktion nochmal aufgerufen, aber dann ist fak nicht mehr null und es wird kein Speicher mehr reserviert. Daraus ergibt sich meines Erachtens eine Gesamt-Speicherkomplexitaet von O(n)
In deinem speziellen Fall ist das nicht dramatisch. Der Stack-Wuchs (was ein Wort) belaeuft sich auf O(n), weil jede Funktion sich selbst nur einmal aufruft. (D.h. es wird insgesamt n mal fakultaet() aufgerufen.) Das waeren dann zusammen mit dem Heap O(n+n) = O(2n). Und da wir konstanten kuerzen bleibt wieder nur O(n) uebrig. (Die lineare Kurve ist zwar durch "2n" in der Tat steiler, aber immernoch linear. Und "linear" ist alles, was wir ausdruecken wollen) Und vielleicht das noch als kleine Anmerkung (von der du dich aber nicht verwirren lassen sollst): Wenn du deine Funktion so umbaust, dass du eine Tail-recursion hast, dann hast du nicht mal mehr den Stack, der mitwaechst.
Du meint, weil ich aus O(2n) ein O(n) gemacht habe? Fall ja, dassn:Ein Stack-Overflow ist bei der O-Notationsbetrachtung nicht Punkt. Bei der O-Notation wird nur betrachtet "in welcher Form" etwas wächst (linear, quadratisch, logarithmisch,...). Merke auch, dass ein Programm mit Speicherverbrauch O(9283239n) auf O(n) gekürzt würde, obwohl es ne ganze Menge Speicher frisst.
@@lerneninverschiedenenforme7513 sorry war gestern schon spät ^^' ja es gibt 2 for loops und deswegen dacht ich, dass es automatisch n^2 ist. Danke für die Antwort! Ist eigentlich eh einleuchtend.
@@sebastiand.5023 Ich hoffe du hast es verstanden :) Du haettest nur deswegen n^2, wenn du "n" mal eine Schleife durchlaeufst, in der du "n" mal eine Schleife durchlaeufst: ----- for ( n mal ) for (n mal ) ----- also n × n fuer das Bsp eben ist ja ------ for (n mal) for (log(n) mal) ------ also n × log(n)
Hier ein besserer Weg zum Lösen der Fakultät mit Rekursion: public static int fakultät(int n) { if (n == 1) return n; else return fakultät(n - 1) * n; }
Am besten guckst du dazu im Internet, falls es dich interessiert (Mathematisch muss der Grenzwert bei kleinen Os gegen Null gehen). Insgesammt gibt es soweit ich weisz 5 oder 6 verschiedene Symbole in diesem Zusammenhang. Am wichtigsten sind aber soweit ich weisz nur die groszen O s. Ich persoenlich wuerde es erst nachgucken, wenn ich in der Literatur drueber stolper.
Das kommt ganz darauf an, was du unter "optimiert" verstehst. Allgemein wuerde ich davon ausgehen, dass er es nicht kann. IdR. heiszt "Laufzeitkomplexitaet verbessern" = "Anderer Algorithmus". Ich glaube nicht, dass Compiler z.Zt. sowas leisten koennen.
@@lerneninverschiedenenforme7513 Wenn ein Algorithmus nur eine Schleife(ohne Body) hat mit O(n) und diese vom Compiler weg optimiert wird hat der Algorithmus nurnoch O(1) ?!
@@FilmfanOliver1992 Nein, das ist falsch. Der algorithmus hat immer noch Komplexitaet O(n). Weil es (z.B. ein Groeszenvergleich fuer eine Sortierfunktion) dann immernoch fuer jedes Element gemacht werden. D.h. es ist egal, ob ich schreibe: data[3]; for (int i = 0; i != 3; ++i){ doSomething(data[i]); } Oder ob ich schreibe: doSomething(data[0]); doSomething(data[1]); doSomething(data[2]); Je mehr Elemente du hast, desto mehr Funktionsaufrufe hast du - und zwar proportional. 5 Element => 5 aufrufe (egal ob Schleife oder ohne Schleife). Anmk. Vergiss auch nicht, dass O(1) (Achtung, jetzt nicht O(n)) auch 10.000 Zeilen Code sein koennen. Aber diese 10.000 Zeilen werde nicht mehr oder weniger, wenn deine Daten mehr oder weniger werden.
Erstmal ohne deine Frage direkt zu beantworten: Ich denke das kannst du so machen (wenn ich es richtig verstehe). Dann zu deiner eigentlichen Frage: 'Wie "man" das macht'. Das kann ich nicht (mehr) beantworten. Da aber im Endeffekt nur das Ergebnis ( = die Klassifizierung des Algorithmus / des Codes) wichtig ist, ist das "man" meines Erachtens sowieso nicht so wichtig.
danke, ich habe eine frage wenn wir for{for{if}else}}} haben und bei else steht eine Anweisung wie n+= (a[i]+a[j]) *x; oder n += a[i-1]-n wie sollen wir rechnen? ist O(n) oder O(1)? wann sollen wir wissen ist O(lg(n)) ???
> wie sollen wir rechnen? ist O(n) oder O(1)? Ich gehe davon aus, dass du fragst nur wegen dem "if". Versuche das Problem runterzubrechen: "(a[i]+a[j]) *x" hat nichts mit der Groesse von n zu tun, also O(1). Aendert sich der "Aufwand" "a[i-1]-n" zu berechnen, wenn n groesser wird? > wann sollen wir wissen ist O(lg(n)) ??? Das ist nicht boese gemeint: Ich empfehle dir an deiner Grammatik zu arbeiten. Sonst laeufst du Gefahr, dass Leute nicht verstehen, was du von ihnen willst. Schreib eventuell deinen Satz in Microsoft Word und lasse ihn korrigieren.
Wenn ich vereinfachen muss und es lautet O(1/n + 10) ist das Ergebnis dann O(1) weil für n gegen unendlich das Ganze gleich null ist? Oder wird die Konstante ignoriert? Ich weiß es ist ein sehr theoretisches Beispiel, da 1/n wohl kaum in einem Programm auftaucht, aber in Probeklausuren hab ich Aufgaben in der Form häufiger gesehen.
Kleines Update, hatte doch noch mal die Gelegenheit den Prof zu fragen, also es zählt ja immer der höchste Exponent und bei einer Konstanten kann man sich immer n^0 dazu denken und dieser ist eben höher als n^-1. Trotzdem danke für die schnelle Antwort.
Bester Abschluss beim Erklärvideo : "Ich hoffe, das Video hat nicht zu sehr verwirrt."
"Benutzt niemals i und j beide!"
Mein Professor: "Benutzt i und j in diesem Fall."
Jeder Programmierer macht das :D
9:07 der war ja so trocken, dass ich ein Lachflash bekommen hab :D
freut mich, dass ich amüsieren kann :)
das war irgendwie echt so stumpf da musst ich auch erstmal lachen hahaha
2:34 mein Professor: Hold my variables
Vielen Dank! Und auch Danke für die Empfehlung, hilft extrem wenns der Abend vor der Klausur ist :D
Danke !! Ich war voll am Verzweifeln wegen des Themas aber jetzt habe ich das echt gecheckt. In 1 Woche bestätigt mir das dann mein Prof hoffentlich! :D
danke fürs video! hat mir auf jeden Fall mehr Klarheit im Thema verschafft.
:)
Danke für die Erklärung! Hab bald Informatik Klausur und meine Lehrerin hat es nicht verständlich genug erklärt. Habs jetzt verstanden
Sehr verständlich! Bringt mich dem Thema gewiss näher :D
9:07 xD ich hatte es erwartet aber dann haste kurz ne pause gemacht und ich dachte oh er lässt es dabei und dann kahm die supper worstlaufzeit auf die ich gewartet habe und ich habe mich gefreut :,D
Danke, hat sehr fürs Mathestudium geholfen und btw sehr angenehme Stimme :)
Das Video hat sehr geholfen. Danke sehr.
Besser als mein Professor
Super Video!
Sehr schön erklärt, hättest du vielleicht auch etwas zu O(√) ?
Ad-hoc faellt mir dazu leider kein Beispiel ein :/
k = n; i = 1
while(k>0)
{ k = k - i;
i = i + 1;
}
Danke dir !!
Tolle Erklärung Danke !
Sehr gutes Video. danke :D
Hey danke viel mals. Hat mir echt geholfen 👍
banger video
Cooles Video, echt toll, aber wie ist es mit der Speicherkomplexität in dem etwas "größeren" Programm ?
Tut mir leid, das bin ich komplett uebergangen. Bei Speicherkomplexitaet bin ich leider nicht ganz so sicher. Sollte aber eigentlich genauso funktionieren:
- In dem Teil rechts oben (fak = new int[n]) werden n Speicherplaetze reserviert. Also O(n)
- Ueber die Rekursion wird dann die Funktion nochmal aufgerufen, aber dann ist fak nicht mehr null und es wird kein Speicher mehr reserviert.
Daraus ergibt sich meines Erachtens eine Gesamt-Speicherkomplexitaet von O(n)
Ja aber bei der Rekusion ist es doch so das der Stack immer weiter "wachst" und da durch die Speicherkomplexität weiter steigt ?
In deinem speziellen Fall ist das nicht dramatisch. Der Stack-Wuchs (was ein Wort) belaeuft sich auf O(n), weil jede Funktion sich selbst nur einmal aufruft. (D.h. es wird insgesamt n mal fakultaet() aufgerufen.)
Das waeren dann zusammen mit dem Heap O(n+n) = O(2n). Und da wir konstanten kuerzen bleibt wieder nur O(n) uebrig. (Die lineare Kurve ist zwar durch "2n" in der Tat steiler, aber immernoch linear. Und "linear" ist alles, was wir ausdruecken wollen)
Und vielleicht das noch als kleine Anmerkung (von der du dich aber nicht verwirren lassen sollst): Wenn du deine Funktion so umbaust, dass du eine Tail-recursion hast, dann hast du nicht mal mehr den Stack, der mitwaechst.
Ja aber es kann aber irgendwann zu einem Stack-Overflow kommen, da wäre doch der Stack-Wuchs relevant ?
Du meint, weil ich aus O(2n) ein O(n) gemacht habe? Fall ja, dassn:Ein Stack-Overflow ist bei der O-Notationsbetrachtung nicht Punkt. Bei der O-Notation wird nur betrachtet "in welcher Form" etwas wächst (linear, quadratisch, logarithmisch,...). Merke auch, dass ein Programm mit Speicherverbrauch O(9283239n) auf O(n) gekürzt würde, obwohl es ne ganze Menge Speicher frisst.
Tolles Video danke !
Eine Frage hätte ich:
Wenn in meiner for schleife folgendes steht:
for(i = 1; i
Du meinst insgesamt sowas wie
for (p = 1; p
@@lerneninverschiedenenforme7513 sorry war gestern schon spät ^^' ja es gibt 2 for loops und deswegen dacht ich, dass es automatisch n^2 ist.
Danke für die Antwort! Ist eigentlich eh einleuchtend.
@@sebastiand.5023 Ich hoffe du hast es verstanden :)
Du haettest nur deswegen n^2, wenn du "n" mal eine Schleife durchlaeufst, in der du "n" mal eine Schleife durchlaeufst:
-----
for ( n mal )
for (n mal )
-----
also n × n
fuer das Bsp eben ist ja
------
for (n mal)
for (log(n) mal)
------
also n × log(n)
Danke Bro!
Hier ein besserer Weg zum Lösen der Fakultät mit Rekursion:
public static int fakultät(int n) {
if (n == 1) return n;
else return fakultät(n - 1) * n;
}
naja fakultät von negativen Zahlen geht ja nicht das muss novh ergänzt werden sonst perfekt
Nice
welche Bedeutung haben denn kleine o´s ?
Am besten guckst du dazu im Internet, falls es dich interessiert (Mathematisch muss der Grenzwert bei kleinen Os gegen Null gehen). Insgesammt gibt es soweit ich weisz 5 oder 6 verschiedene Symbole in diesem Zusammenhang. Am wichtigsten sind aber soweit ich weisz nur die groszen O s. Ich persoenlich wuerde es erst nachgucken, wenn ich in der Literatur drueber stolper.
nice
Könnte ein optimierter Kompiler die Laufzeikomplexität verbessern ?
Das kommt ganz darauf an, was du unter "optimiert" verstehst. Allgemein wuerde ich davon ausgehen, dass er es nicht kann. IdR. heiszt "Laufzeitkomplexitaet verbessern" = "Anderer Algorithmus". Ich glaube nicht, dass Compiler z.Zt. sowas leisten koennen.
@@lerneninverschiedenenforme7513 Es gibt C Compiler die erkennen z.b unnütze for-Schleifen oder If Statements und optimieren den assemblierten Code.
@@FilmfanOliver1992 Zwischen for-Schleifen-Optimierung und Algorithmenumschreibung liegen Welten :)
@@lerneninverschiedenenforme7513 Wenn ein Algorithmus nur eine Schleife(ohne Body) hat mit O(n) und diese vom Compiler weg optimiert wird hat der Algorithmus nurnoch O(1) ?!
@@FilmfanOliver1992 Nein, das ist falsch. Der algorithmus hat immer noch Komplexitaet O(n). Weil es (z.B. ein Groeszenvergleich fuer eine Sortierfunktion) dann immernoch fuer jedes Element gemacht werden.
D.h. es ist egal, ob ich schreibe:
data[3];
for (int i = 0; i != 3; ++i){
doSomething(data[i]);
}
Oder ob ich schreibe:
doSomething(data[0]);
doSomething(data[1]);
doSomething(data[2]);
Je mehr Elemente du hast, desto mehr Funktionsaufrufe hast du - und zwar proportional. 5 Element => 5 aufrufe (egal ob Schleife oder ohne Schleife).
Anmk. Vergiss auch nicht, dass O(1) (Achtung, jetzt nicht O(n)) auch 10.000 Zeilen Code sein koennen. Aber diese 10.000 Zeilen werde nicht mehr oder weniger, wenn deine Daten mehr oder weniger werden.
Geht man hier von Block zu Block if{} und schreibt es dann so auf O(1) + O(1) + O(n) = O(n)?
Erstmal ohne deine Frage direkt zu beantworten: Ich denke das kannst du so machen (wenn ich es richtig verstehe).
Dann zu deiner eigentlichen Frage: 'Wie "man" das macht'. Das kann ich nicht (mehr) beantworten. Da aber im Endeffekt nur das Ergebnis ( = die Klassifizierung des Algorithmus / des Codes) wichtig ist, ist das "man" meines Erachtens sowieso nicht so wichtig.
Gibst es andere Übungsaufgaben?
danke, ich habe eine frage wenn wir for{for{if}else}}} haben und bei else steht eine Anweisung wie n+= (a[i]+a[j]) *x; oder n += a[i-1]-n wie sollen wir rechnen? ist O(n) oder O(1)?
wann sollen wir wissen ist O(lg(n)) ???
> wie sollen wir rechnen? ist O(n) oder O(1)?
Ich gehe davon aus, dass du fragst nur wegen dem "if".
Versuche das Problem runterzubrechen:
"(a[i]+a[j]) *x" hat nichts mit der Groesse von n zu tun, also O(1).
Aendert sich der "Aufwand" "a[i-1]-n" zu berechnen, wenn n groesser wird?
> wann sollen wir wissen ist O(lg(n)) ???
Das ist nicht boese gemeint: Ich empfehle dir an deiner Grammatik zu arbeiten. Sonst laeufst du Gefahr, dass Leute nicht verstehen, was du von ihnen willst. Schreib eventuell deinen Satz in Microsoft Word und lasse ihn korrigieren.
Danke
Wenn ich vereinfachen muss und es lautet O(1/n + 10) ist das Ergebnis dann O(1) weil für n gegen unendlich das Ganze gleich null ist? Oder wird die Konstante ignoriert? Ich weiß es ist ein sehr theoretisches Beispiel, da 1/n wohl kaum in einem Programm auftaucht, aber in Probeklausuren hab ich Aufgaben in der Form häufiger gesehen.
edit: old
@@lerneninverschiedenenforme7513 Vielen Dank für die schnelle Antwort und ja das macht schon Sinn.
Kleines Update, hatte doch noch mal die Gelegenheit den Prof zu fragen, also es zählt ja immer der höchste Exponent und bei einer Konstanten kann man sich immer n^0 dazu denken und dieser ist eben höher als n^-1. Trotzdem danke für die schnelle Antwort.
@@MrChaosplay Vielen Dank fuer das Update hier! Klingt sehr einleuchtend.
Ich habe meine Antwort sicherheitshalber geloescht.
warum wird die 5 weggekürzt?
An welcher Stelle? Zeit?
Wie mich das triggert wenn die geschweiften Klammern in einer eigenen Zeile stehen :D
King