Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Komplexitätsbeweis

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Komplexitätsbeweis

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

aRo
Jungspund

Dabei seit: 25.10.2007
Beiträge: 18

Komplexitätsbeweis

Zitatantwort auf diesen Beitrag erstellen

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 20:28

Nehmen Sie aRo in Ihre Freundesliste auf

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

28.07.2008 21:18

Nehmen Sie Tobias in Ihre Freundesliste auf

aRo
Jungspund

Dabei seit: 25.10.2007
Beiträge: 18

du hast recht, danke dir! Daumen hoch

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

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

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

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]$ und nicht $[latex]O(e^{g(n)})[/latex]$

04.08.2008 12:15

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Komplexitätsbeweis