aRo
Jungspund
Dabei seit: 25.10.2007
Beiträge: 18
 |
|
Hallo!
Zeigen Sie: ![[latex] e^{f(n)} \in O(e^{g(n)}) \Rightarrow f(n) \in O(g(n)) [/latex]](http://www.matheboard.de/latex2png/latex2png.php? e^{f(n)} \in O(e^{g(n)}) \Rightarrow f(n) \in O(g(n)) )
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]](http://www.matheboard.de/latex2png/latex2png.php? e^{f(n)} \in O(e^{g(n)}) \stackrel{?}{\Leftrightarrow} \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0)
Dann würde ja nach Voraussetzung gelten:
![[latex] \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0 [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0 )
Jetzt ist die Frage, welche Voraussetzungen ich genau brauche, damit ich:
![[latex] \lim_{n \to \infty} \frac{f(n)}{g(n)}=0 [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \lim_{n \to \infty} \frac{f(n)}{g(n)}=0 ) 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 20:28 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php? e^{f(n)} \in o(e^{g(n)}) \Rightarrow \lim_{n \to \infty} \frac{e^{f(n)}}{e^{g(n)}}=0)
|
|
|
28.07.2008 21:18 |
|
|
aRo
Jungspund
Dabei seit: 25.10.2007
Beiträge: 18
|
|
du hast recht, danke dir! 
Ist aber schade, wäre ein schönes Werkzeug gewesen 
|
|
|
28.07.2008 22:22 |
|
|
aRo
Jungspund
Dabei seit: 25.10.2007
Beiträge: 18
|
|
ä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]](http://www.matheboard.de/latex2png/latex2png.php? \lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 0 \Rightarrow g \in O(f) \mbox{ ohne } \Theta(f) )
aber
![[latex] \lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 0 \Leftarrow g \in O(f) \mbox{ ohne } \Theta(f) [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 0 \Leftarrow g \in O(f) \mbox{ ohne } \Theta(f) )
gilt nicht.
Da zieht doch auch ein Beispiel:
g(n) = f(n) , dann ist ![[latex] g(n) \in O(f(n)) [/latex]](http://www.matheboard.de/latex2png/latex2png.php? g(n) \in O(f(n)) ) aber ![[latex]\lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 1)
|
|
|
01.08.2008 11:43 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Ich habe nicht groß-O (obere Schranke) sondern klein-o (asymptotisch verschwindend) geschrieben:
![[latex]o(e^{g(n)})[/latex]](http://www.matheboard.de/latex2png/latex2png.php?o(e^{g(n)})) und nicht ![[latex]O(e^{g(n)})[/latex]](http://www.matheboard.de/latex2png/latex2png.php?O(e^{g(n)}))
|
|
|
04.08.2008 12:15 |
|
|
|
