Notationsbeweis < Sonstiges < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen Sie folgende Aufwandsabschätzung für die Symbole O und [mm] \Theta.
[/mm]
[mm] 3^n [/mm] = [mm] O(2^n) [/mm] oder
[mm] 3^n [/mm] = [mm] \Theta(2^n) [/mm] |
mein Ansatz:
[mm] 3^n [/mm] = [mm] O(2^n)
[/mm]
[mm] 3^n [/mm] =< c * [mm] 2^n [/mm] / Division durch [mm] 2^n
[/mm]
[mm] 3^n [/mm] / [mm] 2^n [/mm] =< c
weiter komme ich nicht.
Habe keinen Plan wie ich nun weiter vorgehen soll.
mfg
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:44 Fr 21.03.2008 | | Autor: | Loddar |
Hallo bloody cape,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !!
Ist die Aufgabenstellung auch richtig (und vollständig) abgeschrieben?
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:11 Fr 21.03.2008 | | Autor: | Marcel |
Hallo,
> Beweisen Sie folgende Aufwandsabschätzung für die Symbole O
> und [mm]\Theta.[/mm]
>
> [mm]3^n[/mm] = [mm]O(2^n)[/mm] oder
> [mm]3^n[/mm] = [mm]\Theta(2^n)[/mm]
> mein Ansatz:
>
> [mm]3^n[/mm] = [mm]O(2^n)[/mm]
>
> [mm]3^n[/mm] =< c * [mm]2^n[/mm] / Division durch [mm]2^n[/mm]
>
> [mm]3^n[/mm] / [mm]2^n[/mm] =< c
das ist doch okay, nur fehlt eine Interpretation. Angenommen:
[mm] $3^n=O(2^n)$ [/mm] bei $n [mm] \to \infty$. [/mm] Dann gäbe es ein $0 < C < [mm] \infty$ [/mm] und ein $N [mm] \in \IN$, [/mm] so dass für alle $n [mm] \ge [/mm] N$ gelten würde:
[mm] $|3^n|=3^n \le C*|2^n|=C*2^n$
[/mm]
Dann würde insbesondere
[mm] $\left(\frac{3}{2}\right)^n \le [/mm] C$ für alle $n [mm] \ge [/mm] N$ gelten im Widerspruch zu
[mm] $\left(\frac{3}{2}\right)^n=\left(1+\frac{1}{2}\right)^n \ge 1+\frac{n}{2} \to \infty$ [/mm] bei $n [mm] \to \infty$ [/mm]
(Man beachte die Bernoulli-Ungleichung!)
Jetzt musst Du Dir halt noch Gedanken machen, ob dann vll. [mm] $3^n=\Theta(2^n)$ [/mm] gilt (was aber auch nicht gelten kann, da dann ja insbesondere [mm] $3^n=O(2^n)$ [/mm] gelten müsste).
![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Landau-Symbole#Formale_Definition
Nun kann hier aber auch noch folgendes sein:
1.) Du hast [mm] $3^n$ [/mm] und [mm] $2^n$ [/mm] vertauscht und solltest eigentlich zeigen:
[mm] $2^n=O(3^n)$ [/mm] oder [mm] $2^n=\Theta(3^n)$ [/mm] bei $n [mm] \to \infty$
[/mm]
(Hierbei würde [mm] $2^n=O(3^n)$ [/mm] gelten, aber [mm] $2^n=\Theta(3^n)$ [/mm] wäre falsch, weil [mm] $2^n=\Omega(3^n)$ [/mm] falsch wäre. Die Begründung zu letzterem ist auch oben enthalten, da $f [mm] \in [/mm] O(g) [mm] \gdw [/mm] g [mm] \in \Omega(f)$.)
[/mm]
2.) Bei [mm] $3^n=O(2^n)$ [/mm] soll nicht $n [mm] \to \infty$ [/mm] gelten, sondern was anderes (was mich aber wundern würde).
Daher:
Bitte nochmal die Aufgabe(nstellung) kontrollieren und ggf. korrigieren.
Gruß,
Marcel
|
|
|
| |
|
Danke !
Mit der Lösung bin ich zufrieden !
mfg> Hallo,
>
> > Beweisen Sie folgende Aufwandsabschätzung für die Symbole O
> > und [mm]\Theta.[/mm]
> >
> > [mm]3^n[/mm] = [mm]O(2^n)[/mm] oder
> > [mm]3^n[/mm] = [mm]\Theta(2^n)[/mm]
> > mein Ansatz:
> >
> > [mm]3^n[/mm] = [mm]O(2^n)[/mm]
> >
> > [mm]3^n[/mm] =< c * [mm]2^n[/mm] / Division durch [mm]2^n[/mm]
> >
> > [mm]3^n[/mm] / [mm]2^n[/mm] =< c
>
> das ist doch okay, nur fehlt eine Interpretation.
> Angenommen:
> [mm]3^n=O(2^n)[/mm] bei [mm]n \to \infty[/mm]. Dann gäbe es ein [mm]0 < C < \infty[/mm]
> und ein [mm]N \in \IN[/mm], so dass für alle [mm]n \ge N[/mm] gelten würde:
>
> [mm]|3^n|=3^n \le C*|2^n|=C*2^n[/mm]
>
> Dann würde insbesondere
>
> [mm]\left(\frac{3}{2}\right)^n \le C[/mm] für alle [mm]n \ge N[/mm] gelten im
> Widerspruch zu
>
> [mm]\left(\frac{3}{2}\right)^n=\left(1+\frac{1}{2}\right)^n \ge 1+\frac{n}{2} \to \infty[/mm]
> bei [mm]n \to \infty[/mm]
>
> (Man beachte die Bernoulli-Ungleichung!)
>
> Jetzt musst Du Dir halt noch Gedanken machen, ob dann vll.
> [mm]3^n=\Theta(2^n)[/mm] gilt (was aber auch nicht gelten kann, da
> dann ja insbesondere [mm]3^n=O(2^n)[/mm] gelten müsste).
>
> http://de.wikipedia.org/wiki/Landau-Symbole#Formale_Definition
>
> Nun kann hier aber auch noch folgendes sein:
>
> 1.) Du hast [mm]3^n[/mm] und [mm]2^n[/mm] vertauscht und solltest eigentlich
> zeigen:
> [mm]2^n=O(3^n)[/mm] oder [mm]2^n=\Theta(3^n)[/mm] bei [mm]n \to \infty[/mm]
>
> (Hierbei würde [mm]2^n=O(3^n)[/mm] gelten, aber [mm]2^n=\Theta(3^n)[/mm] wäre
> falsch, weil [mm]2^n=\Omega(3^n)[/mm] falsch wäre. Die Begründung zu
> letzterem ist auch oben enthalten, da [mm]f \in O(g) \gdw g \in \Omega(f)[/mm].)
>
> 2.) Bei [mm]3^n=O(2^n)[/mm] soll nicht [mm]n \to \infty[/mm] gelten, sondern
> was anderes (was mich aber wundern würde).
>
> Daher:
> Bitte nochmal die Aufgabe(nstellung) kontrollieren und
> ggf. korrigieren.
>
> Gruß,
> Marcel
|
|
|
|
