O Notation

[keinnick]

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.....

[[MD]]

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.

P.S:
Ich habe das Gefühl das ich der einzige Ersti hier im Forum bin.....

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 ...

[K-Bal]

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.

[Timothy]

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ß

[sat1911]

Tach zusammen!

Sie ein geeignetes c 2 R und ein n0 2 N angeben.
f(n) = 2n^3 + 5n € O(n3)

gruß

du setzt dir ein "geignetes" c, und rechnest das n0 dazu
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