Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » O-Notation

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

O-Notation

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

idontknowhow10
Grünschnabel

Dabei seit: 29.04.2018
Beiträge: 1

O-Notation

Zitatantwort auf diesen Beitrag erstellen

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:

29.04.2018 16:59

Nehmen Sie idontknowhow10 in Ihre Freundesliste auf

NixJava
unregistriert

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.

29.04.2018 18:43

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » O-Notation