Groß-Oh-Notation < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:50 Mi 18.06.2014 | | Autor: | rsprsp |
| Aufgabe | Beweisen Sie die folgenden Beziehungen
a) log x + [mm] x^{2} [/mm] + [mm] x^{4} \in O(x^{5})
[/mm]
b) 3x log x + 7x [mm] \in [/mm] O(x log x)
c) |sin x| [mm] \in [/mm] O(1)
d) [mm] 3^{n} \in 2^O(n) [/mm] |
Ich versuchte immer die "kleineren" Terme zu kürzen um die beiden größten zu vergleichen.
[mm] log(n)*n^{2}+n^{4} €O(n^{5})
[/mm]
[mm] (log(n))*1+(n^{2})*1+n^{4}
[/mm]
[mm] log(n)€(n^{2})€(n^{4})
[/mm]
d.h
[mm] n^{4} [/mm] * c >= [mm] n^{5}
[/mm]
c >= n
-> wahre Aussage
3n*log(n)+7n €O(n*log(n))
3n*log(n)+7n * c >= n*log(n)
3n*log(n) * c + 7 >= n*log(n)
3n * c + 7 >= n
->falsche Aussage
|sin n| €O(1)
|sin n| * c >= 1
Da die Sinus-Funktion nie über die 1 kommt liegt sie in 1
für c=1/sin n ist stets 1
-> wahre Aussage
Ich habe probiert diese Aufgabe zu lösen, doch meine Ansätze sind deutlich falsch. Könnte mir jemand an Hand eines Beispiels zeigen wie ich das lösen soll? Vor allem die Teilaufgabe (d) mit der ich große Schwierigkeiten habe.
Danke im voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:27 Do 19.06.2014 | | Autor: | Marcel |
Hallo,
> Beweisen Sie die folgenden Beziehungen
> a) log x + [mm]x^{2}[/mm] + [mm]x^{4} \in O(x^{5})[/mm]
> b) 3x log x + 7x
> [mm]\in[/mm] O(x log x)
> c) |sin x| [mm]\in[/mm] O(1)
> d) [mm]3^{n} \in 2^O(n)[/mm]
> Ich versuchte immer die "kleineren"
> Terme zu kürzen um die beiden größten zu vergleichen.
>
>
> [mm]log(n)*n^{2}+n^{4} €O(n^{5})[/mm]
>
> [mm](log(n))*1+(n^{2})*1+n^{4}[/mm]
> [mm]log(n)€(n^{2})€(n^{4})[/mm]
> d.h
> [mm]n^{4}[/mm] * c >= [mm]n^{5}[/mm]
> c >= n
>
> -> wahre Aussage
was machst Du denn hier? (Mal abgesehen davon, dass doch bei $n [mm] \to \infty$
[/mm]
die Ungleichung $n [mm] \le [/mm] c$ für festes $c [mm] \in \IR$ [/mm] falsch wird.) Schlag mal nach:
![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Landau-Symbole
Ich nehme an, ihr macht das nicht mit der (gleichwertigen) Limsup-Definition.
D.h. bei Euch wird wohl (ich nehme zudem an, dass oben der Fall $x [mm] \to \infty$
[/mm]
behandelt wird) bei der a) zu zeigen sein
[mm] $\exists\,$ [/mm] $C > [mm] 0\,$ [/mm] und [mm] $\exists$ $x_0$ [/mm] mit:
[mm] $|f(x)|\,$ $\le$ $C*|g(x)|\,$ [/mm] für alle $x [mm] \ge x_0\,.$
[/mm]
Sei dazu $C > [mm] 0\,$ [/mm] noch unbestimmt, dann schauen wir uns erstmal alle [mm] $x\,$ [/mm] mit
[mm] $|\log(x)+x^2+x^4| \le C*|x^5|$
[/mm]
an. Nehmen wir einschränkungslos [mm] $x_0 \ge [/mm] 1$ an, so gilt für $x [mm] \ge x_0,$ [/mm] dass obige
Ungleichung gleichwertig ist mit
[mm] $\frac{\log(x)}{x^5}+\frac{1}{x^3}+\frac{1}{x} \le C\,.$
[/mm]
Ich nehme an, dass [mm] $\log$ [/mm] der natürliche Logarithmus ist (ansonsten hättest Du
eine kleine Modifikation im Folgenden vorzunehmen - bzw. man sollte sich
überlegen, dass auch im Falle des Zehnerlogarithmus die folgende
Abschätzung übernommen werden kann). Dann ist Dir vielleicht die
Abschätzung
[mm] $\log(x) \le x\,$
[/mm]
für alle $x > [mm] 0\,$ [/mm] klar?
Wenn wir also, wegen
[mm] $\frac{\log(x)}{x^5}+\frac{1}{x^3}+\frac{1}{x} \le \frac{x}{x^5}+\frac{1}{x^3}+\frac{1}{x}=\frac{1}{x^4}+\frac{1}{x^3}+\frac{1}{x}$
[/mm]
nun ein $C > [mm] 0\,$ [/mm] und ein [mm] $x_0$ [/mm] mit
[mm] $\frac{1}{x^4}+\frac{1}{x^3}+\frac{1}{x} \le [/mm] C$ für alle $x [mm] \ge x_0$
[/mm]
finden, haben wir gewonnen.
Ich behaupte: [mm] $C:=3\,$ [/mm] und [mm] $x_0:=1$ [/mm] tun's. Warum?
P.S. Eine alternative Möglichkeit wäre es hier:
Betrachte (für o.E. $x > [mm] 0\,$) [/mm] die Funktion
$x [mm] \mapsto \left|\frac{\log(x)+x^2+x^4}{x^5}\right|$
[/mm]
und zeige, dass, wenn man diese Funktion auf [mm] $[x_0,\infty)$ [/mm] mit einem [mm] $x_0 [/mm] > 0$
einschränkt, dann die eingeschränkte Funktion nach oben beschränkt ist.
Sowas funktioniert hier durchaus auch mit Mitteln, die aus der Schule
bekannt sind (auch dabei solltest Du vielleicht erstmal o.E. [mm] $x_0 \ge [/mm] 1$ annehmen...)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:22 Do 19.06.2014 | | Autor: | rsprsp |
| Aufgabe | Es geht hier eigentlich um die Aufwandsklassen
log n + [mm] n^{2} [/mm] + [mm] n^{4} [/mm] ∈ [mm] O(n^{5})
[/mm]
O(log n) + [mm] O(n^{2}) [/mm] + [mm] O(n^{4}) [/mm] // O(log n) C [mm] O(n^{2}) [/mm] = [mm] O(n^{2}) [/mm]
[mm] O(n^{2}) [/mm] + [mm] O(n^{4}) [/mm] // [mm] O(n^{2}) [/mm] =C [mm] O(n^{4}) [/mm]
= [mm] O(n^{4}) [/mm] |
Ich habe bisschen abgeguckt was unser Tutor gemacht hat und bin auf das gekommen.
Kann man jetzt annehmen, dass das Ergebnis richtig ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:12 Fr 20.06.2014 | | Autor: | Marcel |
Hallo,
> Es geht hier eigentlich um die Aufwandsklassen
>
> log n + [mm]n^{2}[/mm] + [mm]n^{4}[/mm] ∈ [mm]O(n^{5})[/mm]
> O(log n) + [mm]O(n^{2})[/mm] + [mm]O(n^{4})[/mm] // O(log n) C [mm]O(n^{2})[/mm] =
> [mm]O(n^{2})[/mm]
> [mm]O(n^{2})[/mm] + [mm]O(n^{4})[/mm] // [mm]O(n^{2})[/mm] =C [mm]O(n^{4})[/mm]
> = [mm]O(n^{4})[/mm]
> Ich habe bisschen abgeguckt was unser Tutor gemacht hat
> und bin auf das gekommen.
> Kann man jetzt annehmen, dass das Ergebnis richtig ist?
nein, das kann zwar stimmen, aber Du erklärst da doch gar nichts. Das ist
einfach nur Symbolik.
Was Du vielleicht machen wolltest (übrigens fehlt hier immer noch sowas
wie "bei $n [mm] \to \infty$"):
[/mm]
Es ist
[mm] $\log(n) \in O(n^2)\,.$ [/mm] (Da fehlt dann aber eine Begründung!)
Folglich
[mm] $(\log(n)+n^2) \in O(n^2)\,.$
[/mm]
(Frage an Dich: Für $f(n), g(n) [mm] \in O(n^2):$ [/mm] Warum folgt dann $(f+g)(n) [mm] \in O(n^2)$?)
[/mm]
Weiter gilt
[mm] $O(n^2) \subseteq O(n^4)\,.$ [/mm] (Warum?)
Folglich
[mm] $(\log(n)+n^2+n^4) \in O(n^4)$ [/mm] (da [mm] $n^4 \in O(n^4)$ [/mm] trivial ist!).
Also
[mm] $(\log(n)+n^2+n^4) \in O(n^4)\,.$
[/mm]
Wegen
[mm] $O(n^4) \subseteq O(n^5)$
[/mm]
folgt
[mm] $(\log(n)+n^2+n^4) \in O(n^5)\,.$
[/mm]
Sowas hätte Dein Tutor vielleicht schreiben können, oder er hat das zu dem,
was er da geschrieben hat, vielleicht gesagt.
(Eventuell hat er manches auch ein wenig anders notiert, so wie
[mm] $O(n^2)+O(n^4) \subseteq O(n^4)\,,$
[/mm]
aber das ist ja eher ein wenig Geschmackssache. Zudem kann man anstatt
[mm] $\subseteq$ [/mm] hier auch [mm] $=\,$ [/mm] schreiben, aber das macht man vielleicht nicht,
weil es zum einen eines Beweises bedürfte, und zum anderen die Gleichheit
ja gar nicht wirklich benötigt wird.)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:43 Do 19.06.2014 | | Autor: | Marcel |
Hallo,
> Beweisen Sie die folgenden Beziehungen
> b) 3x log x + 7x
> [mm]\in[/mm] O(x log x)
Tipp: Ist $x [mm] \ge x_0:=e\,,$ [/mm] so ist [mm] $\log(x) \ge \log(e)=1$ [/mm] und infolgedessen
$|3x [mm] \log(x)+7x|=3x \log(x)+7x \le [/mm] 3x [mm] \log(x)+7x\log(x)=10x\log(x)=10*|x \log(x)|$ [/mm] (für alle $x [mm] \ge x_0:=e\,.$)
[/mm]
Also? (Welche Wahl von [mm] $C\,$ [/mm] ist geeignet?)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:23 Do 19.06.2014 | | Autor: | rsprsp |
| Aufgabe | 3n log n + 7n ∈ O(n log n)
O(3n log n) + O(7n) // O(7n) = O(n) // O(3n log n) = O(n log n)
O(n log n) + O(n) // O(n) =C O(n log n)
= O(n log n) |
Hier bin ich soweit zum Ergebnis gekommen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:14 Fr 20.06.2014 | | Autor: | Marcel |
Hallo,
> 3n log n + 7n ∈ O(n log n)
> O(3n log n) + O(7n) // O(7n) = O(n) // O(3n log n) = O(n
> log n)
> O(n log n) + O(n) // O(n) =C O(n log n)
> = O(n log n)
> Hier bin ich soweit zum Ergebnis gekommen
schreibe doch mal ein wenig mehr dazu:
Klar ist
$3n [mm] \log(n)+7n \in [/mm] O(n [mm] \log(n))+O(n)\,.$
[/mm]
Wegen
$O(n) [mm] \subseteq [/mm] O(n [mm] \log(n))$ [/mm] (warum)
folgt daher
...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:50 Do 19.06.2014 | | Autor: | Marcel |
Hallo,
> Beweisen Sie die folgenden Beziehungen
> c) |sin x| [mm]\in[/mm] O(1)
Dir ist doch sicher
[mm] $|\sin(x)|$ $\le$ $1\,$
[/mm]
geläufig (das gilt ja sogar für alle $x [mm] \in \IR$). [/mm] Damit wird diese Aufgabe trivial;
klar, oder?
(Du hast zu zeigen: Es gibt ein $C > [mm] 0\,$ [/mm] und ein [mm] $x_0$ [/mm] so, dass für alle $x [mm] \ge x_0$
[/mm]
[mm] $|\sin(x)|$ $\le$ $C\,$
[/mm]
folgt...)
> d) [mm]3^{n} \in 2^O(n)[/mm]
Meinst Du hier [mm] $3^n \in O(2^n)$? [/mm] Oder was bedeutet [mm] $2^{O(n)}$? [/mm] Jedenfalls wirst
Du
[mm] $3^n \in O(2^n)$ [/mm] ($n [mm] \to \infty$)
[/mm]
nicht beweisen können - denn ist $C > [mm] 0\,,$ [/mm] so folgt
[mm] $|3^n|=3^n \le C*|2^n|=C*2^n$
[/mm]
[mm] $\iff$ $(3/2)^n$ $\le$ $C\,.$
[/mm]
Aber [mm] $(3/2)^n \to \infty$ [/mm] bei $n [mm] \to \infty$...
[/mm]
Leicht wäre es
[mm] $2^n \in O(3^n)$
[/mm]
nachzuweisen...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:26 Do 19.06.2014 | | Autor: | rsprsp |
Hier geht es genau um:
[mm] 3^{n} \in 2^{O(n)}
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:16 Fr 20.06.2014 | | Autor: | Marcel |
Hallo,
> Hier geht es genau um:
>
> [mm]3^{n} \in 2^{O(n)}[/mm]
was ist
[mm] $2^{O(n)}$?
[/mm]
Ist das
[mm] $\text{Pot}(O(n))$???
[/mm]
Gruß,
Marcel
|
|
|
|
