Landau-Symbolik Erklärung < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:45 So 05.06.2011 | | Autor: | Blubie |
Hallo, wir hatten in der Vorlesung nur einen Zwei-Zeiler zur Landau-Symnbolik und sollen nun eine ganze Kette von Beweisen mit dieser Symbolik machen. Ich verstehe jedoch die Schreibweise überhaupt nicht ... Könnte mir jemand erklären, was das z.b. bedeutet:
[mm] O(a_{n}) [/mm] + [mm] O(a_{n}) [/mm] = [mm] O(a_{n})
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:11 So 05.06.2011 | | Autor: | Teufel |
Hi!
Wenn du g=O(f) hast, dann bedeutet das, ganz grob gesagt, dass g höchstens so stark im Unendlichen wächst wie f. Für die exakte Definition, schaue nochmal in dein Skript.
Die Definition, unter der ich das erklärt bekommen habe, war folgende:
f=O(g) (eigentlich [mm] f\in [/mm] O(g), weil O(g) eine Menge ist) [mm] \gdw [/mm] es gibt ein c>0, für das es ein [mm] x_0 [/mm] gibt, sodass für alle [mm] x>x_0 [/mm] gilt: [mm] $|f(x)|\le [/mm] c*|g(x)|$.
z.B. ist [mm] x^3=O(2*x^3+x). [/mm] Wähle z.B. c=10, [mm] x_0=0. [/mm] Dann ist [mm] |x|^3\le 10*|2x^3+x| [/mm] für alle x>0.
Für das Symbol gelten dann so einige Rechenregeln, z.B. ist O(a*f)=O(f) für Konstanten a>0, weil man die in der Definition einfach zum c dazuschlagen kann.
Siehe auch hier: ![[]](/images/popup.gif) Klick.
Deine Schreibweise da ist mir aber auch unbekannt. Eventuell soll man anwenden, dass O(f)+O(g)=O(f+g) ist (hattet ihr mal so etwas in der Art? ansonsten kannst du das z.B. mit meiner Definition einfach zeigen).
Dann hast du [mm] O(a_n)+O(a_n)=O(2a_n)=O(a_n) [/mm] nach dem von mir oben genannten.
|
|
|
|
