Groß Theta bestimmen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:14 Do 06.02.2014 | | Autor: | knorke |
Hallo Leute.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
In einem Skript zur "Diskreten Mathematik für Informatiker" steht folgende Definition:
---
Für f, g: [mm] \IN \to \IR
[/mm]
[mm] \Theta [/mm] (g(n) = [mm] \{f(n) | es\ existieren\ Konstanten\ C_1, C_2 > 0\ und\ ein\ n_0 \in \IN, so\ dass\ C_1|g(n)| <= |f(n)| <= C_2|g(n)| fuer\ alle\ n>= n_0 \}
[/mm]
---
Ich möchte nun von folgendem f(n) die Abschätzung finden:
f(n) = [mm] \wurzel[3]{n^2} [/mm] - 4n [mm] log(n^2)
[/mm]
Prinzipiell muss man ja nur "von innen nach außen" die einzelnen Teile betrachten.
Was mich allerdings verunsichert ist das minus zwischen den beiden Teilen.
Wie muss ich damit umgehen? Es gibt ja keine negative Abschätzung laut oben stehender Definition. Oder irre ich mich da?
Ich würde nun folgendes machen und hoffe ihr könnt mir sagen ob hier irgendwo ein Fehler ist.
Nun denn:
f(n) = [mm] n^{\bruch{2}{3}} [/mm] - 4n2log(n)
[mm] \Rightarrow [/mm] (Konstanten weglassen):
[mm] n^\bruch{2}{3} [/mm] - n log(n)
[mm] \Rightarrow [/mm] (da [mm] n^\bruch{2}{3} [/mm] <= [mm] n^1 [/mm] = n):
n - n log(n)
Hier bin ich mir nun nicht mehr sicher:
n log(n) wächst schneller als n [mm] \Rightarrow [/mm] g(n) = n log(n).
Hier habe ich das minus einfach "ignoriert".
Ist das richtig so?
Vielen Dank.
|
|
| |
|
Hallo,
> In einem Skript zur "Diskreten Mathematik für
> Informatiker" steht folgende Definition:
>
> ---
> Für f, g: [mm]\IN \to \IR[/mm]
>
> [mm]\Theta[/mm] (g(n) = [mm]\{f(n) | es\ existieren\ Konstanten\ C_1, C_2 > 0\ und\ ein\ n_0 \in \IN, so\ dass\ C_1|g(n)| <= |f(n)| <= C_2|g(n)| fuer\ alle\ n>= n_0 \}[/mm]
>
> ---
> Ich möchte nun von folgendem f(n) die Abschätzung
> finden:
>
> f(n) = [mm]\wurzel[3]{n^2}[/mm] - 4n [mm]log(n^2)[/mm]
>
> Prinzipiell muss man ja nur "von innen nach außen" die
> einzelnen Teile betrachten.
> Was mich allerdings verunsichert ist das minus zwischen
> den beiden Teilen.
Das Minus kann dir erstmal egal sein. Das wird nur relevant, wenn sich beide Teile "gleich schnell" entwickeln. Zum Beispiel wäre es bei einer Funktion der Form [mm] $\sqrt{n} [/mm] - [mm] \sqrt{n+1}$ [/mm] relevant, dann könnte man nicht einfach die einzelnen Teile betrachten. (*)
Hier siehst ja aber unten an deiner Rechnung, dass ohnehin der zweite Summand das Verhalten von $f$ im Unendlichen bestimmt.
> Wie muss ich damit umgehen? Es gibt ja keine negative
> Abschätzung laut oben stehender Definition. Oder irre ich
> mich da?
Du siehst in der Definition, dass da überall Beträge stehen. Wir reden hier also über $|f(n)|$ und streng genommen muss das abgeschätzt werden. Natürlich werden durch den Betrag nicht alle Minusse in $f(n)$ zu Plussen (man muss sich immer noch Gedanken machen, ob sich zwei Summanden evtl. rausheben, s.o. (*)), aber es liefert dir die Legitimation, unten in deiner Rechnung am Ende das Minus nicht mehr zu beachten (siehe (**)).
> Ich würde nun folgendes machen und hoffe ihr könnt mir
> sagen ob hier irgendwo ein Fehler ist.
> Nun denn:
>
> f(n) = [mm]n^{\bruch{2}{3}}[/mm] - 4n2log(n)
>
> [mm]\Rightarrow[/mm] (Konstanten weglassen):
> [mm]n^\bruch{2}{3}[/mm] - n log(n)
>
> [mm]\Rightarrow[/mm] (da [mm]n^\bruch{2}{3}[/mm] <= [mm]n^1[/mm] = n):
> n - n log(n)
>
> Hier bin ich mir nun nicht mehr sicher:
> n log(n) wächst schneller als n [mm]\Rightarrow[/mm] g(n) = n
> log(n).
Ja.
> Hier habe ich das minus einfach "ignoriert".
> Ist das richtig so?
Ja. (**)
Du hast alles richtig gemacht.
Trotzdem sollte dir klar sein, dass deine Schritte zwar wunderbar den Gedankengang wiedergeben, aber kein Beweis sind.
Evtl. hilft es dir, wenn du dir klar machst, dass die Definition von [mm] $\Theta(g(n))$ [/mm] äquivalent ist zu:
$0 < [mm] \liminf_{n\to\infty}\frac{|f(n)|}{|g(n)|} [/mm] $, $ [mm] \limsup_{n\to\infty}\frac{|f(n)|}{|g(n)|} [/mm] < [mm] \infty$.
[/mm]
Das heißt, du beweist deine Vermutung für $g(n) = [mm] n\log [/mm] (n)$, indem du diese beiden Sachen nachrechnest. Hier genügt es sogar zu zeigen, dass
[mm] $\lim_{n\to\infty}\frac{|f(n)|}{|g(n)|} \in [/mm] (0, [mm] \infty)$,
[/mm]
weil der Limes existiert.
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:25 Fr 07.02.2014 | | Autor: | knorke |
Hi.
Erst mal vielen Dank für deine wirklich hilfreiche Antwort und die Zeit die du dir für die Beantwortung genommen hast!!!
> > Ich möchte nun von folgendem f(n) die Abschätzung
> > finden:
> >
> > f(n) = [mm]\wurzel[3]{n^2}[/mm] - 4n [mm]log(n^2)[/mm]
> >
> > Prinzipiell muss man ja nur "von innen nach außen" die
> > einzelnen Teile betrachten.
> > Was mich allerdings verunsichert ist das minus zwischen
> > den beiden Teilen.
>
> Das Minus kann dir erstmal egal sein. Das wird nur
> relevant, wenn sich beide Teile "gleich schnell"
> entwickeln. Zum Beispiel wäre es bei einer Funktion der
> Form [mm]\sqrt{n} - \sqrt{n+1}[/mm] relevant, dann könnte man nicht
> einfach die einzelnen Teile betrachten. (*)
> Hier siehst ja aber unten an deiner Rechnung, dass ohnehin
> der zweite Summand das Verhalten von [mm]f[/mm] im Unendlichen
> bestimmt.
Stimmt, das leuchtet mir ein. Danke.
>
> > Wie muss ich damit umgehen? Es gibt ja keine negative
> > Abschätzung laut oben stehender Definition. Oder irre ich
> > mich da?
>
> Du siehst in der Definition, dass da überall Beträge
> stehen. Wir reden hier also über [mm]|f(n)|[/mm] und streng
> genommen muss das abgeschätzt werden. Natürlich werden
> durch den Betrag nicht alle Minusse in [mm]f(n)[/mm] zu Plussen (man
> muss sich immer noch Gedanken machen, ob sich zwei
> Summanden evtl. rausheben, s.o. (*)), aber es liefert dir
> die Legitimation, unten in deiner Rechnung am Ende das
> Minus nicht mehr zu beachten (siehe (**)).
>
> > Ich würde nun folgendes machen und hoffe ihr könnt mir
> > sagen ob hier irgendwo ein Fehler ist.
> > Nun denn:
> >
> > f(n) = [mm]n^{\bruch{2}{3}}[/mm] - 4n2log(n)
> >
> > [mm]\Rightarrow[/mm] (Konstanten weglassen):
> > [mm]n^\bruch{2}{3}[/mm] - n log(n)
> >
> > [mm]\Rightarrow[/mm] (da [mm]n^\bruch{2}{3}[/mm] <= [mm]n^1[/mm] = n):
> > n - n log(n)
> >
> > Hier bin ich mir nun nicht mehr sicher:
> > n log(n) wächst schneller als n [mm]\Rightarrow[/mm] g(n) = n
> > log(n).
>
> Ja.
>
> > Hier habe ich das minus einfach "ignoriert".
> > Ist das richtig so?
>
> Ja. (**)
> Du hast alles richtig gemacht.
>
> Trotzdem sollte dir klar sein, dass deine Schritte zwar
> wunderbar den Gedankengang wiedergeben, aber kein Beweis
> sind.
>
> Evtl. hilft es dir, wenn du dir klar machst, dass die
> Definition von [mm]\Theta(g(n))[/mm] äquivalent ist zu:
>
> [mm]0 < \liminf_{n\to\infty}\frac{|f(n)|}{|g(n)|} [/mm],
> [mm]\limsup_{n\to\infty}\frac{|f(n)|}{|g(n)|} < \infty[/mm].
>
> Das heißt, du beweist deine Vermutung für [mm]g(n) = n\log (n)[/mm],
> indem du diese beiden Sachen nachrechnest. Hier genügt es
> sogar zu zeigen, dass
>
> [mm]\lim_{n\to\infty}\frac{|f(n)|}{|g(n)|} \in (0, \infty)[/mm],
>
> weil der Limes existiert.
>
Danke das habe ich verstanden :)
Da im Skript keinerlei Limes Superior/Inferior angegeben ist und in den Beispielen des Skripts lediglich "stumpf" das Laufzeitverhalten abgeschätzt wurde, ist es vermutlich nicht erlaubt es zu nutzen. Hier wurde im Skript zumindest nichts dergleichen bewiesen bzw. eingeführt. Soweit ich das in den Beispielen und alten Klausuren der vergangenen Vorlesungen sehe, ist die einfache Abschätzung ausreichend und kein Beweis notwendig.
Im Skript steht auch eine Formel für die Dreiecksungleichung:
|x + y| <= |x| + |y|
Diese Aussage kann ich doch bestimmt auch nutzen um eine Abschätzung nach oben vorzunehmen oder?
Für das oben angegebene Beispiel würde dies ja bedeuten:
|f(n)| <= [mm] |n^\bruch{2}{3}| [/mm] + |-4n [mm] log(n^2)|
[/mm]
In diesem Falle wäre das Minus ja auch nicht relevant. Oder mache ich was falsch?
Was mache ich eigentlich wenn ich dann z.B. folgendes habe:
f(n) = log (n!) ( [mm] n^\bruch{2}{3} [/mm] - 4n [mm] log(n^2))?
[/mm]
log(n!) wächst langsamer als als log [mm] (n^n); [/mm] + Argumentation von oben. [mm] \Rightarrow [/mm]
f(n) <= n log (n) * (n log (n)) [mm] \Rightarrow n^2 log^2 [/mm] (n)
Vielen Dank!!
|
|
|
| |
|
Hallo,
> Erst mal vielen Dank für deine wirklich hilfreiche Antwort
> und die Zeit die du dir für die Beantwortung genommen
> hast!!!
Kein Problem :)
> > Du hast alles richtig gemacht.
> >
> > Trotzdem sollte dir klar sein, dass deine Schritte zwar
> > wunderbar den Gedankengang wiedergeben, aber kein Beweis
> > sind.
> >
> > Evtl. hilft es dir, wenn du dir klar machst, dass die
> > Definition von [mm]\Theta(g(n))[/mm] äquivalent ist zu:
> >
> > [mm]0 < \liminf_{n\to\infty}\frac{|f(n)|}{|g(n)|} [/mm],
> > [mm]\limsup_{n\to\infty}\frac{|f(n)|}{|g(n)|} < \infty[/mm].
> >
> > Das heißt, du beweist deine Vermutung für [mm]g(n) = n\log (n)[/mm],
> > indem du diese beiden Sachen nachrechnest. Hier genügt es
> > sogar zu zeigen, dass
> >
> > [mm]\lim_{n\to\infty}\frac{|f(n)|}{|g(n)|} \in (0, \infty)[/mm],
>
> >
> > weil der Limes existiert.
> >
> Danke das habe ich verstanden :)
>
> Da im Skript keinerlei Limes Superior/Inferior angegeben
> ist und in den Beispielen des Skripts lediglich "stumpf"
> das Laufzeitverhalten abgeschätzt wurde, ist es vermutlich
> nicht erlaubt es zu nutzen. Hier wurde im Skript zumindest
> nichts dergleichen bewiesen bzw. eingeführt. Soweit ich
> das in den Beispielen und alten Klausuren der vergangenen
> Vorlesungen sehe, ist die einfache Abschätzung ausreichend
> und kein Beweis notwendig.
OK.
> Im Skript steht auch eine Formel für die
> Dreiecksungleichung:
> |x + y| <= |x| + |y|
> Diese Aussage kann ich doch bestimmt auch nutzen um eine
> Abschätzung nach oben vorzunehmen oder?
Ja.
> Für das oben angegebene Beispiel würde dies ja
> bedeuten:
> |f(n)| <= [mm]|n^\bruch{2}{3}|[/mm] + |-4n [mm]log(n^2)|[/mm]
> In diesem Falle wäre das Minus ja auch nicht relevant.
> Oder mache ich was falsch?
Nein, das ist richtig. Du kannst nun das Minus auch weglassen, d.h.
$|f(n)| [mm] \le n^{\frac{2}{3}} [/mm] + 4n [mm] \log(n^2)$.
[/mm]
(Beträge sind unnötig, da alles positiv).
Das kannst du nun noch weiter abschätzen:
$|f(n)| [mm] \le [/mm] 8 [mm] \cdot \Big(n^{\frac{2}{3}} [/mm] + n [mm] \log (n)\Big) [/mm] = 8 [mm] n^{\frac{2}{3}}\cdot \Big(1 [/mm] + [mm] n^{\frac{1}{3}}\log(n)\Big) \le [/mm] 8 [mm] n^{\frac{2}{3}}\cdot \Big(n^{\frac{1}{3}}\log(n) [/mm] + [mm] n^{\frac{1}{3}}\log(n)\Big) \le [/mm] 16 n [mm] \log(n)$.
[/mm]
Damit hättest du dann den einen Teil der Definition formal nachgerechnet.
Mit Limites geht es aber schneller :) Dann hättest du:
[mm] $\frac{|f(n)|}{n\log(n)} [/mm] = [mm] \left|\frac{1}{n^{\frac{1}{3}}\log(n)} - 8\right| \to [/mm] 8$
und der Beweis wäre fertig.
> Was mache ich eigentlich wenn ich dann z.B. folgendes
> habe:
> f(n) = log (n!) ( [mm]n^\bruch{2}{3}[/mm] - 4n [mm]log(n^2))?[/mm]
> log(n!) wächst langsamer als als log [mm](n^n);[/mm] +
> Argumentation von oben. [mm]\Rightarrow[/mm]
> f(n) <= n log (n) * (n log (n)) [mm]\Rightarrow n^2 log^2[/mm] (n)
Ja, aber das ist eine zu grobe Schranke. Das heißt, du schätzt mit $n! [mm] \le n^{n}$ [/mm] zu stark ab. Du würdest also nicht die Schranke nach unten für $g(n) = [mm] n^2 \log(n)^2$ [/mm] zeigen können, was für [mm] $\Theta$ [/mm] ja auch gemacht werden muss.
Du könntest entweder einfach $g(n) = [mm] \log(n!)*n*\log(n)$ [/mm] schreiben (also den [mm] $\log(n!)$ [/mm] nicht weiter vereinfachen), oder die ![[]](/images/popup.gif) Stirling-Formel benutzen.
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:56 Sa 08.02.2014 | | Autor: | knorke |
Hallo Stefan,
vielen Dank für die Beantwortung! Du hast mir sehr geholfen das ganze besser zu Verstehen.
Die Stirling-Formel war mir auch nicht bekannt. Steht komischerweise auch nicht im Skript obwohl diese doch sehr hilfreich ist.
Danke und
viele Grüße
Adrian
|
|
|
|
