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
@@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)
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.
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.
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.
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.
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.
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; }
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.
