Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » O-Notation » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Die letzten 2 Beiträge
NixJava

[latex]n_0[/latex] ist die Stelle, ab der [latex]f[/latex] die obere Schranke bildet. Das ist in der Grafik auch so angedeutet. Über das [latex]n_0[/latex] muss nicht viel bekannt sein. Wichtig ist nur, dass es existiert.

Die Landau-Symbole abstrahieren das Laufverhalten asymptotisch. Das bedeutet, konstante Faktoren und Summanden können "gestrichen werden". So ist zum Beispiel [latex]4n^2 + 3 \in O(n^2)[/latex]. Der Hintergedanke dieser Reduktion besteht darin, dass die genaue Laufzeit von der verwendeten Hardware abhängt. Durch eine größere Leistung kann ich den Algorithmus um einen konstanten Faktor beschleunigen.

Das [latex]c[/latex] in der Definition übernimmt genau diese Rolle. In meinem obigen Beispiel kann ich [latex]c=5[/latex] wählen und erhalte [latex]4n^2 + 3 \le 5n^2[/latex]. Für [latex]n=1[/latex] gilt diese Gleichung nicht. Das muss sie auch nicht! Es reicht aus, wenn ein [latex]n_0[/latex] existiert, so dass für alle [latex]n \ge n_0[/latex] die Ungleichung erfüllt ist. Und so ein [latex]n_0[/latex] existiert offensichtlich.
idontknowhow10 O-Notation

Meine Frage:
Hallo, es geht sich um Notationen.

Könnte mir jemand diese Definition erklären?
Bzw. wofür das c genau steht?
Steht es für eine Zahl, mit der ich meine Funktion multiplizieren kann, damit sie immer die obere Schranke bildet?


Meine Ideen:
Die Definition lautet ja in einem Satz:

g Element von O(f), genau dann wenn, es mindestens ein c größer 0 gibt. n_0 mit jedem N ist größer gleich n_0. 0 ist kleiner gleich g(n) ist kleiner gleich c*f(n)

Wäre das soweit korrekt?

Ich versteh nicht ganz, was mir der Teil sagen soll:
n_0 mit jedem N ist größer gleich n_0

idontknowhow10 hat dieses Bild (verkleinerte Version) angehängt:
Zwischenablage01.jpg