(Twitter)
Ich würde keine foreach loop verwenden, ist zwar prinzipiell Pseudocode, Du mußt aber erklären, wo Du das n her nimmst (die Komplexität das zu ermitteln könnte ja theoretisch ziemlich groß sein, theoretisch sogar bestimmend für die Komplexität, daher am Besten angeben), mach ne for 1..n loop und gut
O(1) kann nicht sein, wie willst Du eine Summe über n Elemente in einem Schritt (bzw. einer konstanten Anzahl von Schritten) machen? Das muß mindestens O(n) sein, in Deinem Fall wohl O(2n) weil Du ja die n ermitteln mußt, somit ist das O(n) sein.
Bei Aufgabe 2 ist Dir am Ende ein kleiner Fehler passiert (wobei ich den Exponenten vom 2ten n nicht lesen kann). Laß uns das mal ohne die Formel (die wird wohl stimmen, habs nicht nachgeprüft) analysieren. Du hast T(0) = 1 und T(n)=T(n-1)+n, also T(1)=T(0)+n=1+n, T(2)=T(1)+n=1+n+n, ... Man sieht schnell wie der Hase läuft, da kommt wohl für T(n) = 1+ n + .... + n womit das n eben n mal vorkommt. Somit muß (T(n) =1 + n^2) sein, was (O(n^2)) entspricht.
Laß uns mal die letzten 3 Zeilen Deiner Rechnung betrachten: (= \sum\limits_{d=0}^{n} 1^{d} f(n-d)) (= \sum\limits_{d=0}^{n} n-d) (= n + (n-1) + (n-2) + ... + (n-(n-1)) + (n-n) # n-n=0 lassen wir weg damit haben wir genau n Summanden!) (= n + n + ... + n - 1 - 2 - 3 - ... - (n-1)) (= n^2 - \frac{(n-1)(n-2)}{2}) (\frac{(n-1)(n-2)}{2} < \frac{n^2}{2}) (= n^2 - \frac{n^2}{2}) (= \frac{n^2}{2}) und das ist ja ganz sicher auch (O(n^2)) Damit dürfte die Komplexität von Aufgabe 2 O(n^2) und nicht O(n) sein.
Punkte: 45
Bei meiner frage kann ich wohl nicht "antworten", sondern nur kommentieren und deshalb kein Bild hinzufügen, deshalb siehe bild zu meiner Frage oben in Hauptthread
::: ich verstehe die letzten 3 Zeilen hier nicht ganz - falls mir das so überhaupt richtig dargestellt wird?? (hab es in einen "latex-übersetzer" gegeben, weil es hier nicht dargestellt wurde als formel)
1. wieso wird n nun quadiert, woran liegt das?
2. wo kommt der bruch her?
3. ist das "kleinerals"-zeichen nur ein Darstellungsfehler oder gehört das da hin? wenn es da hingehört: Warum?
sorry für die vielen Fragen, aber das thema ist nun wirklich nicht meins :)
- n wird quadriert, weil ja in jeder Klammer ein n steht, die "n" werden zusammengezählt, somit kommt eben "n" genau "n" mal vor und das ergibt n*n = n^2.
2. Übrig bleibt 1+2+3+4+...+(n-1), das ist der "kleine Gauß". Wie berechnet man die Summe aller Zahlen von 1 bis n? Genau, mit n(n+1)/2. Da die Zahlen nur bis (n-1) gehen, sollte da eigentlich stehen "(n-1)n/2", was sich durch Einsetzen von "n-1" für das "n" in den kleinen Gauß einfach zeigen läßt (oder auch mit "n*(n+1)/2 - n"), hier ist mir ein kleiner Fehler passiert, spielt aber im weiteren keine Rolle, es wird ja auf "kleiner" abgeschätzt und da stimmts wieder.
3. das mit dem "Kleinerals"-Zeichen dient nur zur Abschätzung, man hätte auch rechnen können, hab ich mir gespart :) Mit der Abschätzung kann man zeigen, daß, obwohl mehr abgezogen wird als notwendig, sich die Komplexität von n^2 nicht auf n verringert. Wenn Du willst, kannst Du natürlich rechnen und das dann abschätzen.
ach ja, warum hier im Board mathjax nicht funktioniert (wie im Matheboard) hab ich leider auch noch nicht begriffen, wäre schon prima... :(
─ 3des 02.11.2020 um 21:56jetzt hab ich es glaub ich auch verstanden. Danke
Ich hatte auch nix anderes erwartet ;)
Wenn man sich ein wenig damit beschäftigt, dann ist das kein Hexenwerk!
Markdown wird unterstützt.
hi
─ danielainformatik 02.11.2020 um 12:17danke für die erklärung und den tipp mit der "normalen" schleife. das ist viel sinniger!
dass es eigentlich nicht O(1) sein kann, sollte eigentlich fast klar sein, hab mich etwas verunsichern lassen.
zu 2 meld ich mich gleich noch, hab da noch eine Frage