O-Notation < Sonstiges < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:21 Mi 07.05.2008 | | Autor: | jboss |
| Aufgabe | Sei $g: [mm] \IN \to \IR^{+}$. [/mm] Beweisen Sie
$o(g(n)) [mm] \cap [/mm] w(g(n)) = [mm] \emptyset$ [/mm] |
Hallo leibe Mathefreunde,
fobige Aufgabe bereitet mir Kopfzerbrechen. Intuitiv ist mir ganz klar, dass die Menge der Funtionen $f(n)$, die echt kleiner wachsen als $g(n)$ nicht zugleich echt schneller wachsen können. Allerdings habe ich Probleme einen gescheiten Beweisansatz zu finden :-(
Habe mir zuallererst die Definition der Notationen aufgeschrieben, die da wären:
$o(g(n)) := [mm] \{ f(n) | \limes_{n\rightarrow\infty} \bruch{f(n)}{g(n)} = 0\} [/mm] = [mm] \{ f(n) | (\forall c > 0), (\exists n_0 > 0), (\forall n \ge n_0) : f(n) < c * g(n)\}$
[/mm]
$w(g(n)) := [mm] \{ f(n) | \limes_{n\rightarrow\infty} \bruch{f(n)}{g(n)} = \infty\} [/mm] = [mm] \{ f(n) | (\forall c > 0), (\exists n_0 > 0), (\forall n \ge n_0) : f(n) > c * g(n)\}$
[/mm]
Demnach könnte ich doch einen Widerspruchsbeweis führen oder?
Angenommen es gilt: $f(n) [mm] \in [/mm] o(g(n))$ und $f(n) [mm] \in [/mm] w(g(n))$
Dann müsste doch gelten:
$ f(n) < c * g(n) < f(n) $
$ = [mm] \bruch{f(n)}{g(n)} [/mm] < c < [mm] \bruch{f(n)}{g(n)}$
[/mm]
Das ist ein Widerspruch und somit ist die Behauptung belegt.
Ist das so korrekt?
Gruss Jakob
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:36 Fr 09.05.2008 | | Autor: | M.Rex |
Hallo
> Sei [mm]g: \IN \to \IR^{+}[/mm]. Beweisen Sie
> [mm]o(g(n)) \cap w(g(n)) = \emptyset[/mm]
> Hallo leibe
> Mathefreunde,
> fobige Aufgabe bereitet mir Kopfzerbrechen. Intuitiv ist
> mir ganz klar, dass die Menge der Funtionen [mm]f(n)[/mm], die echt
> kleiner wachsen als [mm]g(n)[/mm] nicht zugleich echt schneller
> wachsen können. Allerdings habe ich Probleme einen
> gescheiten Beweisansatz zu finden :-(
> Habe mir zuallererst die Definition der Notationen
> aufgeschrieben, die da wären:
> [mm]o(g(n)) := \{ f(n) | \limes_{n\rightarrow\infty} \bruch{f(n)}{g(n)} = 0\} = \{ f(n) | (\forall c > 0), (\exists n_0 > 0), (\forall n \ge n_0) : f(n) < c * g(n)\}[/mm]
>
> [mm]w(g(n)) := \{ f(n) | \limes_{n\rightarrow\infty} \bruch{f(n)}{g(n)} = \infty\} = \{ f(n) | (\forall c > 0), (\exists n_0 > 0), (\forall n \ge n_0) : f(n) > c * g(n)\}[/mm]
>
> Demnach könnte ich doch einen Widerspruchsbeweis führen
> oder?
> Angenommen es gilt: [mm]f(n) \in o(g(n))[/mm] und [mm]f(n) \in w(g(n))[/mm]
>
> Dann müsste doch gelten:
> [mm]f(n) < c * g(n) < f(n)[/mm]
> [mm]= \bruch{f(n)}{g(n)} < c < \bruch{f(n)}{g(n)}[/mm]
>
> Das ist ein Widerspruch und somit ist die Behauptung
> belegt.
>
> Ist das so korrekt?
Das sieht gut aus. Evtl. solltest du noch ein wenig ausführlicheren Text drumherumschreiben.
>
> Gruss Jakob
>
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:35 Di 27.05.2008 | | Autor: | jboss |
Hallo,
kommt ein wenig verspätet, aber trotzdem ein Dankeschön an dich 
lg Jakob
|
|
|
|
