Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Wachstum von Funktionen
Hallo, kann mir Jemand die Art von Aufgaben erklären?
Seien f, g : N → R Funktionen.
Zeige oder widerlege: Ω(f(n)) ∩ O(g(n)) ̸= ∅ ⇒ f(n) ∈ Ω(g(n))
oder
Seien f, g : N → R Funktionen.
Zeige oder widerlege: Ω(f(n)) ∩ O(g(n)) ̸= ∅ ⇒ f(n) ∈ O(g(n))
verstehe die leider absolut überhaupt nicht und würde diese nur ungern komplett auslassen in meiner Klausur.
Falls es hier wen gibt, der Experte ist und sein Wissen mit mir teilen möchte, würde ich mich sehr darüber freuen! 
Danke im Voraus!
Du meinst [quote=audavid]
Hallo, kann mir Jemand die Art von Aufgaben erklären?
Seien f, g : N → R Funktionen.
Zeige oder widerlege: Ω(f) ∩ O(g) ̸= ∅ ⇒ f ∈ Ω(g)
oder
Seien f, g : N → R Funktionen.
Zeige oder widerlege: Ω(f) ∩ O(g) ̸= ∅ ⇒ f ∈ O(g)[/quote]
f ist die Funktion. f(n) ein Funktionswert i. Allg. Von mir aus kannst du statt f auch f(.), f(\cdot) oder n \mapsto f(n) schreiben.
-
Behauptung: [m]Ω(f) ∩ O(g) ̸= ∅ ⇒ f ∈ Ω(g)[/m]: [m]Ω(f) ∩ O(g) ̸= ∅[/m], d.h. es gibt eine Funktion, die mindestens so schnell wächst wie f und maximal so schnell wächst wie g. Muss f dann zwangsläufig mindestens so schnell wachsen wie g?
Du findest für diese Behauptung ein einfaches Gegenbeispiel mit niedrigen Monomen. -
Behauptung: [m]Ω(f) ∩ O(g) ̸= ∅ ⇒ f ∈ O(g)[/m]. Sei also h im Schnitt. Dann f \in O(h) und h \in O(g). Wie folgt nun f \in O(g)?
Ich könnte dir die Definition von Ω und O übrigens nicht aus dem Stegreif sagen. Da bräuchte ich wohl auch 1-2 Minuten, um auf die korrekte formale Definition zu kommen. Der Punkt ist, dass es hier reicht Intuition über diese mathematischen Objekte zu besitzen. Die Eigenschaft, die ich in 2 benutzt habe (“wie folgt nun …?”), muss einfach intuitiv gelten, sonst wäre der ganze O Formalismus “moralisch kaputt”