 Landau - ThetaNotation |
xole_X
Grünschnabel
Dabei seit: 23.10.2007
Beiträge: 9
 |
|
Hallo zuerst mal an alle 
ich soll folgendes beweisen bzw widerlegen:![[latex]2^{n} = \Theta(2^{\frac{n}{2} } )[/latex]](http://www.matheboard.de/latex2png/latex2png.php?2^{n} = \Theta(2^{\frac{n}{2} } ))
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
![[latex]\lim_{n \to \infty }\frac{2^n}{2^{n/2}} = \lim_{n \to \infty }{2^{n-n/2}} = \lim_{n \to \infty }2^{n/2} = \infty [/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lim_{n \to \infty }\frac{2^n}{2^{n/2}} = \lim_{n \to \infty }{2^{n-n/2}} = \lim_{n \to \infty }2^{n/2} = \infty )
die aussage ist also falsch? genügt dies als beweis soweit?
|
|
20.04.2008 19:26 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
|
|
20.04.2008 20:54 |
|
|
xole_X
Grünschnabel
Dabei seit: 23.10.2007
Beiträge: 9
|
|
| Zitat: |
Original von Tobias
Nun widerlegt man leicht ![[latex]2^n \in \mathcal{O}(2^{\frac{n}{2}})[/latex]](http://www.matheboard.de/latex2png/latex2png.php?2^n \in \mathcal{O}(2^{\frac{n}{2}})) indem man zeigt, dass es kein c und kein m gibt, so dass gilt:
![[latex]2^n \leq c \cdot 2^{\frac{n}{2}} \quad \forall n \geq m[/latex]](http://www.matheboard.de/latex2png/latex2png.php?2^n \leq c \cdot 2^{\frac{n}{2}} \quad \forall n \geq m) |
![[latex]\frac{2^n}{2^{\frac{n}{2}} } \leq c \quad \forall n \geq m[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\frac{2^n}{2^{\frac{n}{2}} } \leq c \quad \forall n \geq m)
![[latex]2^{\frac{n}{2}} \leq c \quad \forall n \geq m[/latex]](http://www.matheboard.de/latex2png/latex2png.php?2^{\frac{n}{2}} \leq c \quad \forall n \geq m)
ein solcher Index n >m kann net existieren, da c eine feste konstante ist. aber wie beweis ich das?
|
|
|
20.04.2008 22:00 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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. ![[latex]n \geq \max\{2(\log_2(c)+1), m \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n \geq \max\{2(\log_2(c)+1), m \})
|
|
|
20.04.2008 22:12 |
|
|
xole_X
Grünschnabel
Dabei seit: 23.10.2007
Beiträge: 9
|
|
| Zitat: |
Original von Tobias
Mögliche Wahl ist z.B. |
ich verstehe den rechten teil nicht so ganz...was soll das sein? eine methode, die das maximum zwischen 2log(c) +2 und m berechnet?
|
|
|
20.04.2008 23:30 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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).
|
|
|
21.04.2008 17:00 |
|
|
|
