Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
ONotation & Komplexitätstheorie
Guten Abend zusammen,
ich musste mich mir hier registrieren in der Hoffnung dass mir einer hier helfen kann? Ich hab mittlerweile das halbe Internet durchgeforstet allerdings hab ich einfach absolut keine Ahnung wie ich folgende Aufgabe lösen soll:
Gegeben seien die beiden Komplexitätsfunktionen f, g: N → N mit f(n) = n^2 + 5n^4 + 6
und g(n) = 8n^4. Zeigen Sie, dass gilt: f(n) = O(g(n)).
Schätzen Sie zum Nachweis der Behauptung f(n) geeignet nach oben hin ab.
Ich möchte gar nicht dass mir jemand die Aufgabe löst sodern lediglich eine Art Anleitung gibt wie ich hier vorgehen soll? ich habe absolut kein plan - mich interessiert es jedoch sehr wie man zu einer lösung kommt
Würde mich wirklich freuen, wenn mir jemand helfen könnte!
Das Problem ist das n^2. Es könnte ja sein, dass n^2 mit steigenden Werten von n “gemütlich mitwächst”, so dass f(n) nicht kleiner oder gleich g(n) ist für n gegen unendlich (siehe die Definition der O-Notation).
In diesem Sinn - vermute ich - sollst Du zeigen, dass n^2 + 5n^4+6 < 6n^4 ist, ab einer bestimmten Größe von n. Dabei ist natürlich die “6n^4” nicht so entscheidend, 7n^4, 7.5n^4, 8n^4, … würden es genauso tun, wenn sich das in der Rechnung als bequemer erweist.
Guten Morgen,
könntest du mir iwie im Ansatz erklären welcher Rechenschritt denn notwendig ist?
ich habe eine ähnliche Aufgabe vor mir liegen die so aussieht und wie folgt gelöst wurde.
f(n) 2n³ + √n
g(n) = n^4
So dann wurde wie folgt gerechnet:
2n³ + √n = O(n^4)
2n³ + √n <= 2n³ + √n * √n = 2n³ + n <= 2n³ + nnn = 3n³ <= 3n^4
für alle n >= 1
(k = 3, n0 = 1)
Das “k” ist der Vorfaktor aus dem 3n^4 das leuchtet mir noch ein. Problem ist hierbei die allgemeine Rechnung bzw. der Weg? Anhand der Aufgabe schaut es mir so aus, dass versucht wird das Wurzel hin solange zu berechnen bis man dem O(n^4) irgendwie nahe kommt? Ich verstehe den Sinn absolut nicht! Zumal wenn ich dieses Rechenschema auf nun aktuell gestellte Aufgabe übertragen würde, würde es auch einfach nicht aufgehen…
f(n) = n² + 5n^4 + 6
g(n)= 8n^4
Wenn ichs genau nach obigen Schema losen würde siehts wie folgt aus:
n² + 5n^4 + 6 = O(8n^4) | fällt hier schon die Konstante weg ? Die 6 ?
n² + 5n^4 <= n² * n + 5n^4 = n³ + 5n^4 <= n³*n + 5n^4 = n^4 + 5n^4 = 6n^4 <=8n^4
siehste das Problem? iwie stimmt ja da was nicht … deshalb … ich bin iwie auf der Suche nach einem anständigen Rechenweg um Aufgaben wie diese iwie lösen zu können -.-
Ehrlich gesagt sehe ich das Problem nicht. Ist doch alles völlig korrekt. Von der Ungenauigkeit abgesehen, dass O(8n^4) = O(n^4) ist.
Konstanten fallen in der O-Notation sowieso raus. Von daher ists voellig korrekt, beides liegt in O(n^4)
http://www.matheboard.de/archive/478970/thread.html
/thread ?
P.S. Seit wann macht man in MC2 Landau-Notation?