Die letzten 5 Beiträge |
Tobias |
Ich habe nicht groß-O (obere Schranke) sondern klein-o (asymptotisch verschwindend) geschrieben:
und nicht |
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:
aber
gilt nicht.
Da zieht doch auch ein Beispiel:
g(n) = f(n) , dann ist aber |
aRo |
du hast recht, danke dir!
Ist aber schade, wäre ein schönes Werkzeug gewesen
|
Tobias |
Deine Äquivalenz kann nicht gelten. Setze z.B. f(n) = g(n).
Es gilt |
aRo |
Komplexitätsbeweis
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! |