O-Kalkül < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:52 So 01.04.2012 | | Autor: | bandchef |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | Beweisen oder widerlegen sie:
$2^{n+1} = O(2^n)$ |
Hi Leute!
Ich wage grad mein ersten Gehversuche mit den Landausymbolen. Ich hab mal so angefangen:
Definition von O: $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)$
Für welche Werte gilt $\underbrace{2^{n+1}}{=g(n)} = \underbrace{O(2^n)}_{f(n)}$ mit $g(n) \leq c \cdot f(n)$?
$\lim_{n \to \infty} \frac{g(n)}{f(n)} = \lim_{n \to \infty} \frac{2^{n+1}}{2^n} = ...$
Ab dieser Stelle weiß ich aber dann leider nicht mehr weiter... Stimmt das soweit? Aber was soll ich hier nun weiter tun?
Könnt ihr mir helfen?
|
|
| |
|
Hiho,
> Für welche Werte gilt [mm]\underbrace{2^{n+1}}{=g(n)} = \underbrace{O(2^n)}_{f(n)}[/mm]
Eine Kleinigkeit:
Du meinst wohl eher
[mm] $\underbrace{2^{n+1}}_{=g(n)} [/mm] = [mm] O\left(\underbrace{2^n}_{f(n)}\right)$
[/mm]
> Ab dieser Stelle weiß ich aber dann leider nicht mehr
> weiter... Normalerweise hab ich an dieser Stelle dann immer
> den Limes über g(n) gebildet. Aber was soll ich hier tun?
Ja, hier hast du nun aber, dass der Grenzwert beidseitig gegen unendlich geht und somit kannst du diesen "kleinen Trick" hier nicht anwenden 
Aber es geht hier viel einfacher: Bedenke einfach, dass [mm] $2^{n+1} [/mm] = [mm] 2*2^n$
[/mm]
Wähle also einfach $c=2$, was steht dann da?
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:08 So 01.04.2012 | | Autor: | bandchef |
Bin mittlerweile selbst draufgekommen:
[mm] $\lim_{n \to \infty} \frac{g(n)}{f(n)} \leq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} \leq [/mm] c [mm] \Leftrightarrow \frac{2^{n+1}}{2^n} \leq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} \frac{2^n \cdot 2^1}{2^n} \leq [/mm] c [mm] \Leftrightarrow [/mm] 2 [mm] \leq [/mm] c$
Stimmt das dann so? Wie würdest du den Antwortsatz schreiben? Das ist grad noch das schwierige... Was ist hier nun Bewiesen oder widerlegt?
|
|
|
| |
|
Hiho,
> Bin mittlerweile selbst draufgekommen:
>
> [mm]\lim_{n \to \infty} \frac{g(n)}{f(n)} \leq c \Leftrightarrow \lim_{n \to \infty} \leq c \Leftrightarrow \frac{2^{n+1}}{2^n} \leq c \Leftrightarrow \lim_{n \to \infty} \frac{2^n \cdot 2^1}{2^n} \leq c \Leftrightarrow 2 \leq c[/mm]
>
> Stimmt das dann so? Wie würdest du den Antwortsatz
> schreiben? Das ist grad noch das schwierige... Was ist hier
> nun Bewiesen oder widerlegt?
Mal ganz davon ab, dass da Betragsstriche fehlen um den Bruch, solltest du dir klarmachen, warum es ausreicht, die Sache mit dem Grenzwert zu machen. Dieser kommt ja in der ursprünglichen Definition gar nicht vor!
Und die Frage ist ja nun, ob es so ein c gibt, so dass das oben gilt.
Gibt es das?
Also bitte nicht einfach nur machen, sondern deine Schritte erklären (und vorallem verstehen!)
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:37 Mo 02.04.2012 | | Autor: | bandchef |
Der lim gilt, da $g(n) [mm] \in [/mm] O(f(n))$. So haben wir das zumindestens aufgeschrieben.
Die Betragsstriche fehlen in der Tat. Sorry.
Ich kann jetzt allerdings wirklich nicht sagen, ob es nun so ein c gibt oder nicht. Wie macht man das an dieser Stelle?
|
|
|
| |
|
Hiho,
> Der lim gilt, da [mm]g(n) \in O(f(n))[/mm]. So haben wir das
> zumindestens aufgeschrieben.
Dann merke dir das so. Im Allgemeinen muss dieser Grenzwert aber nicht mehr existieren, darum schreibt man an der Stelle normalerweise [mm] $\limsup$, [/mm] der im Gegensatz zum [mm] $\lim$ [/mm] immer existiert. Existiert der Grenzwert aber, so ist er gleich. Insofern ist deine Aussage so ganz falsch auch nicht
> Ich kann jetzt allerdings wirklich nicht sagen, ob es nun
> so ein c gibt oder nicht. Wie macht man das an dieser
> Stelle?
Dann schreiben wir das doch nochmal sauber auf, dann wirst du selbst drauf kommen.
Wir wollen wissen, ob [mm] $2^{n+1} \in O(2^n)$, [/mm] d.h. wir müssen prüfen, ob es ein [mm] $c\in\IR^+$ [/mm] gibt, so dass
[mm] $\lim_{n\to\infty} \bruch{2^{n+1}}{2^n} \le [/mm] c$
Nun gilt aber [mm] $\lim_{n\to\infty} \bruch{2^{n+1}}{2^n} [/mm] = 2$.
D.h. obige Frage ist äquivalent dazu, ob es ein [mm] $c\in\IR^+$ [/mm] gibt, so dass $2 [mm] \le [/mm] c$ gilt, denn dann wäre [mm] $2^{n+1} \in O(2^n)$.
[/mm]
Gibt es nun so ein c ?
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:36 Di 03.04.2012 | | Autor: | bandchef |
Wenn nun am Schluss $... [mm] \Leftrightarrow [/mm] 2 [mm] \leq [/mm] c$ steht, dann kann ich ja c=3 setzen. C ist dann aus [mm] $\mathbb [/mm] R^+$ und bspw. größer als 2. Wenn ich c=2 wähle, dann wäre es gleich 2 und somit sollte doch dann [mm] $2^{n+1} [/mm] = [mm] O(2^n)$ [/mm] gelten. Sieht du das auch so?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:52 Di 03.04.2012 | | Autor: | Marcel |
Hallo,
> Wenn nun am Schluss [mm]... \Leftrightarrow 2 \leq c[/mm] steht,
> dann kann ich ja c=3 setzen. C ist dann aus [mm]\mathbb R^+[/mm] und
> bspw. größer als 2. Wenn ich c=2 wähle, dann wäre es
> gleich 2 und somit sollte doch dann [mm]2^{n+1} = O(2^n)[/mm]
> gelten. Sieht du das auch so?
wenn die ganze Frage darauf hinausläuft, ob es ein $C [mm] \in \IR^+$ [/mm] so gibt, dass $2 [mm] \le [/mm] C$ (und Gono hat ja begründet, warum das alles darauf hinausläuft):
Na hör' mal, denk' nicht zu kompliziert: Du kennst ganz viele echt positive reelle Zahlen, die [mm] $\ge [/mm] 2$ sind: Die Zahl [mm] $C:=2\,$ [/mm] ist die kleinstmögliche Wahl (in diesem Sinne optimal, weil man halt nicht viel "über die Grenze [mm] $2\,$ [/mm] hinausgehen muss - nämlich gar nicht"). Ebenso: [mm] $C:=e=2.7\ldots$ [/mm] würde auch die Existenz eines $C [mm] \in \IR^+$ [/mm] mit [mm] $C\ge [/mm] 2$ begründen. Natürlich weißt Du auch, dass mit [mm] $C:=3\,$ [/mm] dann eine Zahl [mm] $\ge [/mm] 2$ gefunden ist.
Selbstverständlich kannst Du auch [mm] $C:=\sqrt{\pi}^{4547856384576347568}$ [/mm] wählen, zeigen, dass dieses [mm] $C\,$ [/mm] dann $C [mm] \ge [/mm] 2$ erfüllt und hast damit auch die Existenz eines $C [mm] \in \IR^+$ [/mm] begründet, dass $C [mm] \ge [/mm] 2$ erfüllt.
Anders gesagt kann man das Ergebnis von Gono hier auch so interpretieren:
Du hast hier gesehen, dass [mm] $2^{n+1} \red{\notin} O(2^n)$ [/mm] gleichbedeutend damit wäre, dass [mm] $\IR^+$ [/mm] durch [mm] $2\,$ [/mm] nach oben beschränkt wäre - was natürlich Humbug ist.
Fazit:
Ja: [mm] $2^{n+1} \in O(2^n)$ [/mm] (manchmal, gar in der Informatik, wird das auch (meines Erachtens im schlechten Stil) als [mm] $2^{n+1}=O(2^n)$ [/mm] geschrieben)!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:34 Mo 02.04.2012 | | Autor: | fred97 |
> Beweisen oder widerlegen sie:
>
> [mm]2^{n+1} = O(2^n)[/mm]
>
>
> Hi Leute!
>
> Ich wage grad mein ersten Gehversuche mit den
> Landausymbolen. Ich hab mal so angefangen:
>
> Definition von O: [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]
>
> Für welche Werte gilt [mm]\underbrace{2^{n+1}}{=g(n)} = \underbrace{O(2^n)}_{f(n)}[/mm]
> mit [mm]g(n) \leq c \cdot f(n)[/mm]?
>
> [mm]\lim_{n \to \infty} \frac{g(n)}{f(n)} = \lim_{n \to \infty} \frac{2^{n+1}}{2^n} = ...[/mm]
>
> Ab dieser Stelle weiß ich aber dann leider nicht mehr
> weiter... Stimmt das soweit? Aber was soll ich hier nun
> weiter tun?
>
> Könnt ihr mir helfen?
[mm]2^{n+1} = O(2^n)[/mm] bedeutet doch, dass die Folge [mm] (\bruch{2^{n+1}}{2^n}) [/mm] beschränkt ist.
FRED
|
|
|
|
