Landau - ThetaNotation |
20.04.2008, 19:26 | Auf diesen Beitrag antworten » | ||||
xole_X | Landau - ThetaNotation Hallo zuerst mal an alle ich soll folgendes beweisen bzw widerlegen: Ich hab mir dazu folgendes überlegt: Damit ˜ - Notation stimmt, muss ja g(n)<=f(n)<=g(n) gelten. (f(n) = 2^n und g(n) 2^(0.5n)) Damit f(n) und g(n) gleichschnell wachsen, muss ja f(n)/g(n) = 1 für n-->inf die aussage ist also falsch? genügt dies als beweis soweit? |
||||
|
|||||
20.04.2008, 20:54 | Auf diesen Beitrag antworten » | ||||
Tobias | Vorsicht! Sowohl die Aussage
als auch
sind so nicht richtig. An deiner Stelle würde ich hier mit der Quantorendefinition der Landausymbole arbeiten: Nun widerlegt man leicht indem man zeigt, dass es kein c und kein m gibt, so dass gilt: |
||||
20.04.2008, 22:00 | Auf diesen Beitrag antworten » | ||||
xole_X |
ein solcher Index n >m kann net existieren, da c eine feste konstante ist. aber wie beweis ich das? |
||||
20.04.2008, 22:12 | Auf diesen Beitrag antworten » | ||||
Tobias | Deine umgeformte Ungleichung muss für ALLE n >= m gelten. Die Argumentation ist nun: Egal wie c und m gewählt werden, es gibt stets ein n >= m, das die Ungleichung falsch macht. Mögliche Wahl ist z.B. |
||||
Anzeige | |||||
|
|||||
20.04.2008, 23:30 | Auf diesen Beitrag antworten » | ||||
xole_X |
ich verstehe den rechten teil nicht so ganz...was soll das sein? eine methode, die das maximum zwischen 2log(c) +2 und m berechnet? |
||||
21.04.2008, 17:00 | Auf diesen Beitrag antworten » | ||||
Tobias | n muss größer als das Maximum aus den beiden Teilen sein, um einen Widerspruch zu erreichen. Warum? n muss nach Voraussetzung (Definition von O(.) ) größer sein als m und da c beliebig sein muss, könnte es auch so gewählt sein, dass m > 2*(log(c)+1). |
|