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:
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!
Geschrieben von Tobias am 28.07.2008 um 21:18:
Deine Äquivalenz kann nicht gelten. Setze z.B. f(n) = g(n).
Es gilt
Geschrieben von aRo am 28.07.2008 um 22:22:
du hast recht, danke dir!
Ist aber schade, wäre ein schönes Werkzeug gewesen
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:
aber
gilt nicht.
Da zieht doch auch ein Beispiel:
g(n) = f(n) , dann ist
aber
Geschrieben von Tobias am 04.08.2008 um 12:15:
Ich habe nicht groß-O (obere Schranke) sondern klein-o (asymptotisch verschwindend) geschrieben:
und nicht
Forensoftware: Burning Board, entwickelt von WoltLab GmbH