Komplexitätsbeweis

28.07.2008, 20:28	Auf diesen Beitrag antworten »
aRo	Komplexitätsbeweis Hallo! Zeigen Sie: $[latex] e^{f(n)} \in O(e^{g(n)}) \Rightarrow f(n) \in O(g(n)) [/latex]$ f(n) und g(n) sind monoton steigend und größer null. Ich könnte das über die Definition beweisen. Jetzt frage ich mich aber, ob es auch mit dem limes geht. Ist folgendes äquivalent? $[latex] e^{f(n)} \in O(e^{g(n)}) \stackrel{?}{\Leftrightarrow} \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0[/latex]$ Dann würde ja nach Voraussetzung gelten: $[latex] \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0 [/latex]$ Jetzt ist die Frage, welche Voraussetzungen ich genau brauche, damit ich: $[latex] \lim_{n \to \infty} \frac{f(n)}{g(n)}=0 [/latex]$ folgern kann. Überhabt irgendwelche? Ich kann ja einfach im Zähler und Nenner die ln Funktion anwenden.... Danke für eure Hilfe!


28.07.2008, 21:18	Auf diesen Beitrag antworten »
Tobias	Deine Äquivalenz kann nicht gelten. Setze z.B. f(n) = g(n). Es gilt $[latex] e^{f(n)} \in o(e^{g(n)}) \Rightarrow \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0[/latex]$
28.07.2008, 22:22	Auf diesen Beitrag antworten »
aRo	du hast recht, danke dir! Ist aber schade, wäre ein schönes Werkzeug gewesen
01.08.2008, 11:43	Auf diesen Beitrag antworten »
aRo	ähm...ich bin ein Meister darin mich im nachhinein nochmal zu verwirren: Aber...jetzt denke ich auf einmal, dass du genau die falsche Implikation als richtig voraussetzt. Meiner Meinung nach gilt: $[latex] \lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 0 \Rightarrow g \in O(f) \mbox{ ohne } \Theta(f) [/latex]$ aber $[latex] \lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 0 \Leftarrow g \in O(f) \mbox{ ohne } \Theta(f) [/latex]$ gilt nicht. Da zieht doch auch ein Beispiel: g(n) = f(n) , dann ist $[latex] g(n) \in O(f(n)) [/latex]$ aber $[latex]\lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 1[/latex]$
Anzeige

04.08.2008, 12:15	Auf diesen Beitrag antworten »
Tobias	Ich habe nicht groß-O (obere Schranke) sondern klein-o (asymptotisch verschwindend) geschrieben: $[latex]o(e^{g(n)})[/latex]$ und nicht $[latex]O(e^{g(n)})[/latex]$

Verwandte Themen