Komplexitätsbeweis |
aRo
Jungspund
Dabei seit: 25.10.2007
Beiträge: 18
|
|
Hallo!
Zeigen Sie:
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?
Dann würde ja nach Voraussetzung gelten:
Jetzt ist die Frage, welche Voraussetzungen ich genau brauche, damit ich:
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
|
|
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:
aber
gilt nicht.
Da zieht doch auch ein Beispiel:
g(n) = f(n) , dann ist aber
|
|
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:
und nicht
|
|
04.08.2008 12:15 |
|
|
|