Informatiker Board | Druckvorschau: Landau - ThetaNotation

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)
--- Landau - ThetaNotation (http://www.informatikerboard.de/board/thread.php?threadid=407)

Geschrieben von xole_X am 20.04.2008 um 19:26:

Landau - ThetaNotation

Hallo zuerst mal an alle großes Grinsen

ich soll folgendes beweisen bzw widerlegen: $[latex]2^{n} = \Theta(2^{\frac{n}{2} } )[/latex]$

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]$

die aussage ist also falsch? genügt dies als beweis soweit?

Geschrieben von Tobias am 20.04.2008 um 20:54:

Vorsicht! Sowohl die Aussage

Zitat:

Damit ˜ - Notation stimmt, muss ja g(n)<=f(n)<=g(n) gelten

als auch

Zitat:

Damit f(n) und g(n) gleichschnell wachsen, muss ja f(n)/g(n) = 1 für n-->inf

sind so nicht richtig.

An deiner Stelle würde ich hier mit der Quantorendefinition der Landausymbole arbeiten:

$[latex]2^n \in \Theta(2^{\frac{n}{2}}) \Rightarrow 2^n \in \mathcal{O}(2^{\frac{n}{2}}) \wedge 2^n \in \Omega(2^{\frac{n}{2}})[/latex]$

Nun widerlegt man leicht $[latex]2^n \in \mathcal{O}(2^{\frac{n}{2}})[/latex]$ 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]$

Geschrieben von xole_X am 20.04.2008 um 22:00:

Zitat:

Original von Tobias
Nun widerlegt man leicht $[latex]2^n \in \mathcal{O}(2^{\frac{n}{2}})[/latex]$ 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]$

$[latex]\frac{2^n}{2^{\frac{n}{2}} } \leq c \quad \forall n \geq m[/latex]$

$[latex]2^{\frac{n}{2}} \leq c \quad \forall n \geq m[/latex]$

ein solcher Index n >m kann net existieren, da c eine feste konstante ist. aber wie beweis ich das?

Geschrieben von Tobias am 20.04.2008 um 22:12:

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]$

Geschrieben von xole_X am 20.04.2008 um 23:30:

Zitat:

Original von Tobias
Mögliche Wahl ist z.B. $[latex]n \geq \max\{2(\log_2(c)+1), m \}[/latex]$

ich verstehe den rechten teil nicht so ganz...was soll das sein? eine methode, die das maximum zwischen 2log(c) +2 und m berechnet?

Geschrieben von Tobias am 21.04.2008 um 17:00:

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).