Wachstum von Funktionen, Komplexität, Graphentheorie |
28.02.2016, 23:28 | Nohora | Auf diesen Beitrag antworten » | ||||
Wachstum von Funktionen, Komplexität, Graphentheorie Zeige oder widerlege: f\in O(g), g\in Omega(h) \Rightarrow f\in Theta(h) Meine Ideen: so weit bin ich schonmal: f\leq c_g*g, c_h*h\leq g \Rightarrow c_1*h\leq f\leq c_2*h Nun habe ich einen Lösungsansatz, weiß aber nicht, ob ich das Thema überhaupt im Gröbsten richtig verstanden habe. c_2 = c_g * c_h 0\leq c_1*h\leq f\leq c_2*h\leq c_g*g Somit wäre gezeigt, dass so ein Fall konstruiert werden kann. Mit der Behauptung stehe ich in meiner Lerngruppe jedoch alleine da, daher meine Frage hier im matheboard. |
||||||
29.02.2016, 17:33 | echnaton | Auf diesen Beitrag antworten » | ||||
Man wählt zum Beispiel und . Dann gilt und . Gilt dann auch ? |
||||||
29.02.2016, 18:28 | Nohora1 | Auf diesen Beitrag antworten » | ||||
Danke. Also reicht es einen Fall zu finden wo diese Folgerung nicht erfüllt ist um es zu widerlegen? Ich dachte irgendwie es sei gezeigt wenn dies für eine Konstruktion gehen würde. Gruß |
||||||
29.02.2016, 18:39 | echnaton | Auf diesen Beitrag antworten » | ||||
Genau, für die Widerlegung einer Aussage reicht ein Gegenbeispiel aus. Sollte die Aussage gelten, müsstest du einen vollständigen Beweis erbringen.
Was meinst du mit "eine Konstruktion"? Ich kann deinen obigen Lösungsansatz leider nicht so recht nachvollziehen. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|