Frage von BillHatayu, 96

Mathematik - Landausche Symbolik - Big O Notation - Was ist 'c'? Wer weiß weiter?

Hallo, ich habe eine Definition aus dem Skript als Bild hochgeladen. Ich weiß nicht, wofür c steht.

Bisher kamen nur Beispiele, in denen das Ergebnis 0 war und deshalb nicht c sein konnte, weil c Element R+ ist.

Aber welche Zahl steht für c? Irgend eine Konstante? Gibt es vielleicht ein Beispiel?

Danke für eure Hilfe!

Antwort
von Roach5, 19

Eine weitere Anschauungsweise, die dir das ganze zu verstehen helfen könnte:

Häufiger als das Theta benutzen wir das Omega und das Omikron (oder einfach O).

Wir sagen, dass f(n) in Omega(g(n)) liegt, wenn für N groß genug f größer als ein Vielfaches (c) von g ist, also wenn n > N, dann f(n) > c * g(n).

Du hast also deine Funktionen f und c * g, und ab irgendeinem Punkt wird für immer f über c * g sein.

Außerdem sagen wir, dass f(n) in O(g(n)) liegt, wenn für N groß genug f kleiner als ein Vielfaches (c) von g ist, also wenn n > N, dann f(n) < c * g(n).

Analog wie im ersten Fall ist ab irgendeinem Punkt f immer unter c * g.

f liegt in Theta(g(n)) [was sich bei dir auf dem Blatt findet], wenn f in Omega(g) und O(g) liegt, wenn also ein c * g eine obere Schranke und ein c' * g untere Schranke ist. In allen diesen Fällen ist c einfach irgendeine Konstante, die das Vielfache widerspiegelt, mehr nicht.

Wieso mache ich das? O(g) wird wesentlich häufiger gebraucht in der Informatik, vor Allem bei der Abschätzung von Algorithmischen Laufzeiten. Wenn z.B. ein Sortieralgorithmus zum Sortieren von n Elementen höchstens n * log(n) Schritte braucht, aber einen bereits sortierten Block garnicht sortieren muss (und nur jedes Element einmal durchliest), dann braucht dein Programm mindestens n und höchstens n * log(n) Schritte, du kannst also nicht Theta(n * log(n)) sagen, aber zumindest O(n * log(n)), und das reicht dir meistens. Denn es ist nie schlimm, wenn der Algorithmus schneller läuft als erwartet ;)

LG

Antwort
von BillHatayu, 43

Ich glaube ich habe es verstanden. In der Definition steht ja:
Es gibt ein c aus der Menge R+ für die gilt: ...

Das bedeutet, wenn das Ergebnis des Vergleichs zwischen den zwei Funktionen eine reelle, positive Zahl ist, ist f(n) Element von g(n).

Das heißt das Ergebnis darf nicht negativ, Null oder Unendlich sein.

Kommentar von ELLo1997 ,

Richtig. Stell es dir anschaulich so vor:
Du hast den Quotienten zweier Folgen f und g: f(n)/g(n). Jetz willst du wissen, was die Folgen machen, wenn n riesig groß wird. Wenn f(n) "schneller wächst", geht f(n) anschaulich gesagt schneller gegen unendlich als g(n). Dann ist das Ergebnis des Grenzwerts auch unendlich. Wächst hingegen g(n) schneller, so geht der Bruch schneller gegen 0 (da g(n) im Nenner) als gegen unendlich (vergleiche klein-o Notation).
Die Folgen konkurrieren sozusagen miteinander :-) Wachsen sie nun gleich schnell, dann "gewinnt" keiner und es kommt eine reelle Zahl heraus, quasi wie ein Verhältnis.
Lg

Kommentar von BillHatayu ,

Ahja, das muss ich mir merken!! Sehr anschaulich!
Was studierst du?

Kommentar von ELLo1997 ,

Gerne.^^ Momentan noch Materialwissenschaften, aber ich werde nächstes Jahr auf Physik wechseln. Du?

Kommentar von BillHatayu ,

Cool! Ich studiere Informatik. Wir schätzen damit die Komplexität von Algorithmen ab. Aber bin leider kein Mathe-Profi ^^

Antwort
von ELLo1997, 54

c ist einfach eine positive, reelle Konstante.

Kommentar von BillHatayu ,

Angenommen f(n)=9n^6+3n^3
Was ist dann c?

hier gibt es kein c, oder?

muss c immer eine Zahl sein?

Kommentar von ELLo1997 ,

Die Landau Symbole dienen dazu zwei (!) Folgen in ihrem Wachstum zu vergleichen. Also brauchst du schon eine zweite Folge.

Kommentar von BillHatayu ,

dann wäre der vergleich zB O(n^6)
Also:
lim n gegen Unendlich von: f(n)/g(n)
= lim (9n^6+3n^3)/n^6

Kommentar von BillHatayu ,

Siehst du die Definition vom Bild?
Könntest du mal ein Beispiel machen und zeigen, was c ist?
Muss es eine Zahl im Zähler sein, also eine Zahl von f(n)?

Kommentar von ELLo1997 ,

Ich nehme gleich dein Beispiel:
f(n) = 9n⁶ + 3n³
g(n) = n⁶

f(n) ist genau dann O(g(n)), wenn der Grenzwert lim{x→∞}(f(n)/g(n)) = c, wobei c eine positive reelle Konstante ist.
Also:

lim{x→∞}(f(n)/g(n)) = lim{x→∞}(9n⁶ + 3n³)/(n⁶) = 9 ∈ ℝ⁺
Daraus folgt, dass f(n) in der Tat ein O(g(n)) ist. Die Grenzwertberechnung macht dir keine Probleme oder?

Lg

Kommentar von BillHatayu ,

Okay, vielen Dank, ich glaube, ich habe es verstanden.
Ich dachte immer, was ist c, aber jetzt habe ich verstanden, dass das Ergebnis nur eine positive reelle Zahl (c) sein muss...

Danke!

Aber auf 9 komme ich nicht, weil 
(9n^6 + 3n^3) / n^6 = 9n^3 + 3  (n^3 ausklammern und kürzen)

Also ist lim{n-->∞} 9n^3 + 3 = ∞

Also ist es nicht Element von g(n), oder?

Kommentar von ELLo1997 ,

Ich denke doch, dass du beim herausheben einen Fehler gemacht hast. Schau nochmal nach ;-)

Kommentar von BillHatayu ,

Ich fürchte, das musst du mir erklären.
(9n⁶ + 3n³) wird doch immer schneller wachsen als (n⁶),
deshalb muss 
 lim{n→∞}(9n⁶ + 3n³)/(n⁶)

gegen Unendlich gehen...





Kommentar von ELLo1997 ,

Na gut :-)
(9n⁶ + 3n³)/n⁶
n⁶ im Zähler herausheben:
= (n⁶(9 + 3/n³))/n⁶
n⁶ kürzen:
= 9 + 3/n³
Und das geht für n → ∞ gegen 9, wie man leicht sieht.
Merke dir einfach zur Überprüfung: Wenn du einen Bruch von Polynomen hast, dann ist der Grenzwert davon gleich dem Bruch der Koeffizienten der höchsten (!) Potenzen. Also in diesem Fall zB die Koeffizienten von n⁶.

Kommentar von BillHatayu ,

Das stimmt! 
Danke, hat mir sehr geholfen!

Kommentar von ELLo1997 ,

Kein Problem👍🏼

Antwort
von suziesext07, 57

da hätte ich ehrlich keine Probleme: der Variablen c wird die linke Seite vom Komma zugeschrieben, in Pascal wär das nicht =   sondern  :=   nur eben seitenverkehrt

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten