O Notation beweisen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweise:
Seien f, g : [mm] \IN \mapsto \IR [/mm] zwei Funktionen. Dann gilt:
(i) f ∈ [mm] \Theta(g) [/mm] ⇔ g ∈ [mm] \Theta(f)
[/mm]
(ii) f ∈ [mm] \Theta(g) [/mm] ⇔ f ∈ O(g) und f ∈ [mm] \omega [/mm] (g)
(iii) f ∈ O(g) ⇔ g [mm] \omega [/mm] ∈
|
Leider weis ich nicht im Geringsten wie diese Aufgabe zu lösen ist - wir haben dazu nur sehr dürftiges Material bekommen.
Wenn mir jmd. eine der Aufgaben (z.b. (i) erklären könnte, die den Lösungsweg anfangen und mir sagen wie das Ergebnis aussehen müsste (so dass ich den Mittelteil selbst herleiten muss) wäre mir wahrscheinlich schon sehr geholfen.
Btw: Was eine O Notation ist dürfte ich mittlerweile in den Grundzügen verstanden haben, aber wie man sie beweist oder anwendet leider nicht.
Hoffe auf rasche Hilfe
mfg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:33 Mi 12.12.2007 | | Autor: | Gilga |
Lies dir mal den wikipedia artikel zum thema durch
f [mm] \in \Theta(g) [/mm] heisst f und g unterscheiden sich asymptotisch nur um eine konstante. z.b.
[mm] f=n^4+5n
[/mm]
[mm] g=3*n^4+n^2+9.
[/mm]
abh. vom Resultat f(n)/g(n) und n gegen unendlich def. die Landausymbole
|
|
|
|
