Landau-Symbole < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:32 Do 10.11.2016 | | Autor: | MarcHe |
| Aufgabe | | Zeigen Sie: [mm] $f=\Omega [/mm] (g)$ genau dann, wenn [mm] $g=\mathcal{O} [/mm] (f)$. |
Hallo,
mein Ansatz ist wiefolgt:
1. [mm] $\Rightarrow$: [/mm] Da [mm] $f=\Omega [/mm] (g)$ folgt $C|g(n)| [mm] \le [/mm] |f(n)|$ für alle $n>B$. Da $C >0 $ gilt ebenso $|g(n)| [mm] \le [/mm] C|f(n)|$. Problem: Wenn doch beispielsweise $C=1$ ist, dann kann ich doch nicht einfach aus [mm] $\le$ [/mm] $<$ machen richtig?
2. [mm] $\Leftarrow$: [/mm] Da [mm] $g=\mathcal{O} [/mm] (f)$ folgt $|g(n)| < C|f(n)|$ für alle $n>B$. Das steht ja fast oben, nur mit dem gleichen Problem, dass [mm] $\le \not=<$.
[/mm]
Wie kann ich diese Problem geschickt lösen?
Viele Grüße,
Marc
|
|
| |
|
Hiho,
leider gibt es für die Definition von [mm] $\Omega(g)$ [/mm] zwei sich unterscheidende Definitionen, siehe dazu ![[]](/images/popup.gif) hier bis zum Ende von Abschnitt "Definition".
> Problem: Wenn doch beispielsweise $ C=1 $ ist, dann kann ich doch nicht einfach aus $ [mm] \le [/mm] $ $ < $ machen richtig?
Du hast doch nirgendwo aus einem [mm] $\le$ [/mm] ein $<$ gemacht?
Ich vermute mal, euer [mm] $\mathcal{O} [/mm] (f)$ benötigt ein $<$ statt ein [mm] $\le$?
[/mm]
1.) unterscheidet sich das dann auch von allen anderen Definitionen
2.) Mach dir mal klar, dass das keinen Unterschied macht, ob da [mm] $\le$ [/mm] oder $<$ steht.
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:36 Fr 11.11.2016 | | Autor: | MarcHe |
Also bei uns ist [mm] $\mathcal{O} [/mm] $ mit $<$ und $ [mm] \Omega(g) [/mm] $ mit [mm] $\le$ [/mm] definiert. Macht das so überhaupt Sinn? Bei Wikipedia ist ja beispielsweise durchgängig [mm] $\le$ [/mm] verwendet.
Kann ich mit der unterschiedlichen Definition überhaupt die beschriebene Folgerung machen?
|
|
|
| |
|
Hiho,
gib mal bitte eure Definition konkret und vollständig an, denn nur so kann man dir anständig weiterhelfen.
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:58 Fr 11.11.2016 | | Autor: | MarcHe |
Ok, also:
1. Seien $f,g : [mm] \IN_0 \to \IR$, [/mm] dann gilt [mm] $f=\mathcal{O} [/mm] (g)$, wenn es $B,C [mm] \in \IN_0$ [/mm] gibt, sodass für alle $n > B$ gilt $|f(n)| < C*|g(n)|$.
2. [mm] $f=\Omega [/mm] (g) $ genau dann, wenn es $B,C >0$ gibt mit [mm] $C*|g(n)|\le [/mm] |f(n)|$ für alle $n > B$.
|
|
|
| |
|
Hiho,
du hast völlig recht, mit diesen Definitionen stimmt die zu zeigende Aussage natürlich nicht.
Seien bspw. [mm] $f\equiv [/mm] g [mm] \equiv [/mm] 0$, dann ist $f = [mm] \Omega(g)$, [/mm] da $C*|g(n)| = 0 [mm] \le [/mm] 0 = |f(n)|$
Aber $g = [mm] \mathcal{O}(f)$ [/mm] gilt nicht, da für alle $C>0$ gilt $|g(n)| = 0 [mm] \not< [/mm] 0 = C*|f(n)|$
Insofern hast du das Problem völlig richtig erkannt, die Frage ist nur, wer jetzt den Fehler gemacht hat 
Gruß,
Gono
|
|
|
|
