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

...komplette Frage anzeigen Was ist 'c'? - (Mathematik, Komplexität von Algorithmen, Landausche Symbole)

4 Antworten

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 bewerten Vielen Dank für Deine Bewertung

c ist einfach eine positive, reelle Konstante.

Antwort bewerten Vielen Dank für Deine Bewertung
BillHatayu 03.06.2016, 23:06

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

hier gibt es kein c, oder?

muss c immer eine Zahl sein?

0
ELLo1997 03.06.2016, 23:07

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

0
BillHatayu 03.06.2016, 23:11
@ELLo1997

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

0
BillHatayu 03.06.2016, 23:14
@ELLo1997

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)?

0
ELLo1997 03.06.2016, 23:21

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

0
BillHatayu 03.06.2016, 23:33
@ELLo1997

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?

0
ELLo1997 03.06.2016, 23:37

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

0
BillHatayu 03.06.2016, 23:46
@ELLo1997

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





0
ELLo1997 03.06.2016, 23:55

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

0

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

Antwort bewerten Vielen Dank für Deine Bewertung

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.

Antwort bewerten Vielen Dank für Deine Bewertung
ELLo1997 03.06.2016, 23:33

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

1
BillHatayu 03.06.2016, 23:35
@ELLo1997

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

0
ELLo1997 03.06.2016, 23:42

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

0
BillHatayu 03.06.2016, 23:44
@ELLo1997

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

0

Was möchtest Du wissen?