Informatiker Board | Druckvorschau: Komplexitätsbeweis

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Komplexitätsbeweis (http://www.informatikerboard.de/board/thread.php?threadid=437)

Geschrieben von aRo am 28.07.2008 um 20:28:

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!

Geschrieben von Tobias am 28.07.2008 um 21:18:

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]$

Geschrieben von aRo am 28.07.2008 um 22:22:

du hast recht, danke dir! Daumen hoch

Ist aber schade, wäre ein schönes Werkzeug gewesen Augenzwinkern

Geschrieben von aRo am 01.08.2008 um 11:43:

ä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]$

Geschrieben von Tobias am 04.08.2008 um 12:15:

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]$