Hallo,
Ich habe noch so meine Probleme mit der O Notation. Mein Problem besteht hauptsächlich darin, wie ich die O Notation eines Programmes/Quellcodes bestimme. Wie werden Schleifen, zuweisungen etc gewertet und wie werden diese dann zusammengewürfelt? Mit den Googelergebnissen kann ich nicht viel anfangen. Hat jemand eine gute Quelle oder Arbeitsblätter o.Ä ?
Grüße
P.S:
Ich habe das Gefühl das ich der einzige Ersti hier im Forum bin.....
O Notation
Moderator: Moderatoren
O Notation
Schöne Grüße!
Rechtschreibfehler untermalen meine Kreativität.
Rechtschreibfehler untermalen meine Kreativität.
Re: O Notation
Ich glaube das es so ist, dass sich die Potenz der Laufzeit n mit jedem Schleifendurchlauf um 1 erhöht. Bin mir aber nicht ganz sicher.
Bist Du nicht. Es sind ca. 300 Leute im Forum angemeldet, aber im dritten Semester sind nur noch ca. 180-190 (von ehemals 330) reinen E-Techniker. Dazu kommen noch die Wirt-Ings, jedoch sind nicht alle in diesem Forum angemeldet, sodass es sehr unwahrscheinlich ist, das Du der einzige "Ersti" bist ...keinnick hat geschrieben:P.S:
Ich habe das Gefühl das ich der einzige Ersti hier im Forum bin.....
Ciao [MD]
Re: O Notation
Ohne Rekursion musst du dir meist nur die Anzahl der ineinaner verschalteten Schleifen angucken (deren Größe von n abhängt).
Mit Rekursion wirds oft unübersichtlicher, bei manchen Fällen malt man sich da am besten nen Baum auf.
Mit Rekursion wirds oft unübersichtlicher, bei manchen Fällen malt man sich da am besten nen Baum auf.
Re: O Notation
Tach zusammen!
Hätte mal eine Frage zur Onotation:
Wie schreibt man das korrekt auf?
Zum Beispiel die beiden Aufgaben aus der Klausur SS08:
Zeigen Sie mit Hilfe der De¯nition der O-Notation die folgende Aussage, indem
Sie ein geeignetes c 2 R und ein n0 2 N angeben.
f(n) = 2n^3 + 5n € O(n3)
und
Berechnen Sie mit Hilfe der Rechenregeln der O-Notation das Laufzeitverhalten
der folgenden Funktion.
g(n) =(n log n + n^2)(n^3 + 2)/n
Prinzipiell ja nicht schwer, was da die Lösung ist, aber wüsste gern wie man das jetzt formell korrekt aufschreibt.
danke im voraus
gruß
Hätte mal eine Frage zur Onotation:
Wie schreibt man das korrekt auf?
Zum Beispiel die beiden Aufgaben aus der Klausur SS08:
Zeigen Sie mit Hilfe der De¯nition der O-Notation die folgende Aussage, indem
Sie ein geeignetes c 2 R und ein n0 2 N angeben.
f(n) = 2n^3 + 5n € O(n3)
und
Berechnen Sie mit Hilfe der Rechenregeln der O-Notation das Laufzeitverhalten
der folgenden Funktion.
g(n) =(n log n + n^2)(n^3 + 2)/n
Prinzipiell ja nicht schwer, was da die Lösung ist, aber wüsste gern wie man das jetzt formell korrekt aufschreibt.
danke im voraus
gruß
Re: O Notation
du setzt dir ein "geignetes" c, und rechnest das n0 dazuTimothy hat geschrieben:Tach zusammen!
Sie ein geeignetes c 2 R und ein n0 2 N angeben.
f(n) = 2n^3 + 5n € O(n3)
gruß
oder du setzt ein "geignetes" n0 und rechnest das c dazu.
f(n) = 2n^3 + 5n € O(n^3) =>2n^3+5n < c*n^3 für alle n >= n0
sei c = 3 (das wäre geeignet^^)
=>2n^3+5n <! c*n^3 |c=3
=>2n^3+5n <! 3*n^3 |-2n^3
=>5n < n3 (gilt für alle n>=n0) somit n0=2
lösung c=3 und n0=2
Dieser Post wurde vom user 'sat1911' 1545 mal geändert.
Zuletzt geändert: morgen um 13:37 Uhr.
Zuletzt geändert: morgen um 13:37 Uhr.