Frage zu "groß O" < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:47 Di 03.04.2012 | | Autor: | bandchef |
| Aufgabe | Beweisen oder widerlegen sie, dass gilt:
[mm] $\underbrace{2^{2n}}_{=g(n)} [/mm] = [mm] O(\underbrace{2^n}_{=f(n)})$ [/mm] |
Ich habe so angefangen:
Definition: $O(f(n)) = [mm] \{ g(n) | \exists c \in \mathbb R^+, n_0 \in \mathbb N: \forall n \geq n_0, g(n) \leq c \cdot f(n) \}$
[/mm]
[mm] $\lim_{n \to \infty} \frac{g(n)}{f(n)} \leq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} \frac{2^{2n}}{2^n} \leq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} \frac{e^{2n \cdot ln(2)}}{e^{n \cdot ln(2)}} \leq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} e^{2n \cdot ln(2) - n \cdot ln(2)} \leq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} e^{n \cdot ln(2)} \leq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} 2^n \leq [/mm] c$
Wie kann man da nun weiter vereinfachen? Vielleicht so wie oben geschrieben? Stimmt die Umformung so?
Ich nehm jetzt einfach mal an, dass ich alles richtig umgeformt habe und lasse jetzt ganz am Schluss den limes loslaufen. Dann bekomme ich ja ein "unendlich" raus. Es würde also QUASI lauten: [mm] $\infty \leq [/mm] c$. Dies geht aber nicht also gilt: [mm] $2^{2n} \not= O(2^n)$
[/mm]
Stimmt das so?
PS: Ich weiß, es fehlen Betragsstriche, aber ich weiß nicht wie man die in LaTeX schreibt...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:08 Di 03.04.2012 | | Autor: | leduart |
Hallo
wenn du verwendest dass [mm] 2^{2n}=2^n*2^n [/mm] geht das doch viel schneller? warum über ehoch?
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:09 Mi 04.04.2012 | | Autor: | bandchef |
Oh, du hast Recht. Manchmal sieht man eben den Wald vor lauter Bäumen nicht...
Nichtsdestrotzt steht bei beiden Varianten am Schluss:
[mm] $\lim_{n \to \infty} 2^n \leq [/mm] c$
Was passiert, wenn ich nun den limes laufen lasse? Gilt das nun so?
|
|
|
| |
|
Hiho,
> Ich nehm jetzt einfach mal an, dass ich alles richtig umgeformt habe und lasse jetzt ganz am Schluss den limes loslaufen. Dann bekomme ich ja ein "unendlich" raus. Es würde also QUASI lauten: [mm] $\infty \leq [/mm] c$. Dies geht aber nicht also gilt:
> $ [mm] 2^{2n} \not= O(2^n) [/mm] $
![[ok]](/images/smileys/ok.gif "[ok]")
Wobei die Formulierung noch etwas "unmathematisch" ist.
Ein Limes läuft nicht los, daher bekommst du auch nix raus.
Aber die Annahme, dass so ein c existiert, kannst du aus obigen Überlegungen heraus sofort verneinen 
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:54 Do 05.04.2012 | | Autor: | fred97 |
> Beweisen oder widerlegen sie, dass gilt:
>
> [mm]\underbrace{2^{2n}}_{=g(n)} = O(\underbrace{2^n}_{=f(n)})[/mm]
>
>
>
>
>
>
>
> Ich habe so angefangen:
>
> Definition: [mm]O(f(n)) = \{ g(n) | \exists c \in \mathbb R^+, n_0 \in \mathbb N: \forall n \geq n_0, g(n) \leq c \cdot f(n) \}[/mm]
>
> [mm]\lim_{n \to \infty} \frac{g(n)}{f(n)} \leq c \Leftrightarrow \lim_{n \to \infty} \frac{2^{2n}}{2^n} \leq c \Leftrightarrow \lim_{n \to \infty} \frac{e^{2n \cdot ln(2)}}{e^{n \cdot ln(2)}} \leq c \Leftrightarrow \lim_{n \to \infty} e^{2n \cdot ln(2) - n \cdot ln(2)} \leq c \Leftrightarrow \lim_{n \to \infty} e^{n \cdot ln(2)} \leq c \Leftrightarrow \lim_{n \to \infty} 2^n \leq c[/mm]
>
> Wie kann man da nun weiter vereinfachen? Vielleicht so wie
> oben geschrieben? Stimmt die Umformung so?
>
> Ich nehm jetzt einfach mal an, dass ich alles richtig
> umgeformt habe und lasse jetzt ganz am Schluss den limes
> loslaufen. Dann bekomme ich ja ein "unendlich" raus. Es
> würde also QUASI lauten: [mm]\infty \leq c[/mm]. Dies geht aber
> nicht also gilt: [mm]2^{2n} \not= O(2^n)[/mm]
>
> Stimmt das so?
>
>
> PS: Ich weiß, es fehlen Betragsstriche, aber ich weiß
> nicht wie man die in LaTeX schreibt...
Die Frage, ob [mm] $2^{2n}=O(2^n)$ [/mm] gilt, ist gleichbedeutend mit der Frage, ob die Folge [mm] (\bruch{2^{2n}}{2^n}) [/mm] beschränkt ist.
Du machst das oben mit [mm] \limes_{n\rightarrow\infty} [/mm] . Das ist O.K., wenn der Limes ex. oder = [mm] \pm \infty [/mm] ist. Was aber machst Du bei der Frage , ob
sin(n)=O(1)
gilt ?
FRED
|
|
|
|
