Algorithmenfrage < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:29 Do 28.05.2009 | | Autor: | tina2 |
| Aufgabe | Geben Sie zwei Funktionen f,g: N -> R+ von der Menge der natürlichen Zahlen in die Menge der positiven reellen Zahlen an, so dass weder f=O(g) noch g=O(f) gilt.
Beweisen Sie die geforderten Eigenschaften. |
Hallo,
leider verstehe ich auch hier nicht, was der von uns möchte.
Ich wäre schon froh, wenn ich das verstehen könnte.
(Falles dies das falsche Forum ist, wir haben das im Fach Diskrete Mathematik bekommen. Ich wüsste nicht, wo es sonst hingehört).
Viele Grüße,
tina2
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo tina2,
> Geben Sie zwei Funktionen f,g: N -> R+ von der Menge der
> natürlichen Zahlen in die Menge der positiven reellen
> Zahlen an, so dass weder f=O(g) noch g=O(f) gilt.
> Beweisen Sie die geforderten Eigenschaften.
Ich denke, es reicht, wenn f oder g nicht monoton steigend/fallend sind, und - unmathematisch ausgedrückt - "hin und her springen". Und da scheint es unendlich viele Funktionen zu geben. Was ist z.B. mit [mm]f(n):=n\mod 2[/mm] und [mm]g(n):=n\mod 3[/mm] ?
Die Definition eines Landau-Symbols lautet:
[mm]f\in\mathcal{O}(g):\Leftrightarrow\exists c>0\exists x_0\forall x>x_0:\left|f(x)\right|\le c\cdot{}\left|g(x)\right|[/mm].
Und wenn man sich so das Bild zu [mm]f\![/mm] und [mm]g\![/mm] anschaut, denke ich nicht, daß du mir ein solches [mm]x_0[/mm] und [mm]c\![/mm] geben kannst, wo die Definition gilt.
[ Ich lass mich aber gerne überraschen. ;) ]
[Dateianhang nicht öffentlich]
Gruß V.N.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
|
