---

Geschrieben von idontknowhow10 am 29.04.2018 um 15:59:

  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

---

Geschrieben von NixJava am 29.04.2018 um 17:43:

 

ist die Stelle, ab der die obere Schranke bildet. Das ist in der Grafik auch so angedeutet. Über das 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 . 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 in der Definition übernimmt genau diese Rolle. In meinem obigen Beispiel kann ich wählen und erhalte . Für gilt diese Gleichung nicht. Das muss sie auch nicht! Es reicht aus, wenn ein existiert, so dass für alle die Ungleichung erfüllt ist. Und so ein existiert offensichtlich.