Limeskriterien + eine Aufgabe < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi alle zusammen,
wir haben in der Vorlesung die Limeskriterien aufgeschrieben.
Ein Kriterium ist z. Bsp.
[mm] \limes_{n\rightarrow\infty} \frac{f(n)}{g(n)} [/mm] = c < [mm] \infty \Rightarrow [/mm] f [mm] \in [/mm] O(g)
Bedeutet c < [mm] \infty [/mm] soviel, dass am Schluss im Zähler kein von n abhängiger Term stehen darf? Ich würde sagen ja, aber ich weiß es nicht genau. War gerade eben beim durchgehen etwas verwirrt.
Zudem habe ich noch eine Frage, wie man beweisen kann, dass [mm] e^{\sqrt{n}} \in [/mm] O(n!).
Weil mit n! kann ich nicht wirklich rechnen, ich weiß, dass
n! = n (n-1) ....
Aber sonst auch nichts, d.h. wenn ich mit der puren Definition nicht weiterkomme, habe ich ein Problem. Wie könnte man diesen Beweis führen? Bzw. was sollte man zu der Fakultät noch wissen?
MfG Andi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:50 Mo 29.08.2005 | | Autor: | Loddar |
Hallo Andi!
> Bedeutet c < [mm]\infty[/mm] soviel, dass am Schluss im Zähler kein
> von n abhängiger Term stehen darf?
Der Ausdruck $c \ < \ [mm] \infty$ [/mm] besagt, dass der betrachtete Ausdruck (hier: [mm] $\frac{f(n)}{g(n)}$ [/mm] ) auch konvergent ist. Das heißt, es existiert ein konkreter Wert für den Grenzwert $c_$.
Der Ausdruck [mm] $\limes_{n\rightarrow \infty} [/mm] ... \ = \ c \ [mm] \red{=} [/mm] \ [mm] \pm \infty$ [/mm] beschreibt dann die Divergenz des betrachteten Ausdruckes.
Gruß
Loddar
|
|
|
| |
|
Also bedeutet das, wenn c < [mm] \infty, [/mm] dann dürfte eigentlich kein n im Term vorkommen, sondern nur Konstanten? Weil ansonsten lässt es sich ja nicht konkret berechnen.
Ist das richtig so?
MfG Andi
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:15 Mo 29.08.2005 | | Autor: | Loddar |
Hallo Andi!
> Also bedeutet das, wenn c < [mm]\infty,[/mm] dann dürfte eigentlich
> kein n im Term vorkommen, sondern nur Konstanten? Weil
> ansonsten lässt es sich ja nicht konkret berechnen.
![[notok]](/images/smileys/notok.gif "[notok]") Das stimmt so nicht ...
Ich gebe Dir mal ein Beispiel:
[mm] $\limes_{n\rightarrow\infty}\bruch{6n^2+4}{3n^2-7} [/mm] \ = \ [mm] \bruch{6}{3} [/mm] \ = \ 2 \ =: \ c \ < \ [mm] \infty$
[/mm]
Hier haben wir ja sowohl in Nenner als auch im Zähler jeweils $n_$ auftreten, aber dennoch existiert hier ein Grenzwert $c_$ mit $c \ < \ [mm] \infty$ [/mm] .
Nun etwas klarer?
Gruß
Loddar
|
|
|
| |
|
Hi,
ok, jetzt hab ich's endlich gepeilt, wenn man L'Hopital anwenden würde, dann wäre es ja noch klarer, da sich ja dann das n wegkürzt und dann genau diese 2 stehen bleibt.
Das ganze geht aber gegen unendlich, wenn z.Bsp. [mm] \frac{n^3}{n^2} [/mm] da steht, oder? Weil, dann kann man ja 2x l'Hopital anwenden und man erhält n und das geht ja trivialerweise gegen unendlich.
Also ich hoffe, dass meine folgende Aussagen nun stimmt:
c < [mm] \infty [/mm] gilt dann, wenn entweder ein konstanter Term da steht oder wenn es gegen einen reellen Wert konvergiert, d.h. wenn man z. Bsp. durch l'Hopital die n's beseitigen kann. Ich hoffe, das ist jetzt so ungefähr richtig. Falls es falsch ist, könntest du ein Beispiel machen, wo etwas gegen unendlich konvergiert?
Meiner Meinung ist das immer dann der Fall, wenn [mm] \frac{n^x}{n^y} [/mm] mit x>y gilt.
MfG Andi
PS: Sorry, ich bin in Analysis ein absoluter Versager *gg*, ich denke das hat man gemerkt.
|
|
|
| |
|
Hallo Andi,
Kommen wir mal zu deiner 2ten Teilfrage:
> Zudem habe ich noch eine Frage, wie man beweisen kann, dass
> [mm]e^{\sqrt{n}} \in \mathcal{O}\left(n!\right)[/mm].
>
> Weil mit $n!$ kann ich nicht wirklich rechnen, ich weiß, dass
>
> $n! := n [mm] *\left(n-1\right)* \ldots*1$ [/mm] und $0! := 1$
>
> Aber sonst auch nichts, d.h. wenn ich mit der puren
> Definition nicht weiterkomme, habe ich ein Problem. Wie
> könnte man diesen Beweis führen? Bzw. was sollte man zu der
> Fakultät noch wissen?
Du könntest mal nach der Stirlingschen Näherungsformel schauen.
Allerdings wäre es übertrieben diese Formel hier zu benutzen. Die Definition, die Du oben angegeben hast, liefert dir nämlich schon eine gute Abschätzung für $n!$:
[m]
\begin{array}{ccccccccccccccc}
{n^n} & = & n & * & n & * & \ldots & * & n & {} & {} & * & \ldots & * & n \\
{n!} & = & n & * & {\left( {n - 1} \right)} & * & \ldots & * & {\frac{n}{2}} & {} & {} & * & \ldots & * & 1 \\
{\left(\frac{n}{2}\right)^{\frac{n}{2}}} & = & {\frac{n}{2}} & * & {\frac{n}{2}} & * & \ldots & * & {\frac{n}{2}} & * & 1 & * & \ldots & * & 1
\end{array}
[/m]
Die Faktoren der dritten Gleichung sind jeweils kleiner oder gleich den Faktoren von $n!$. Das Umgekehrte gilt für die Faktoren von [mm] $n^n$. [/mm] Damit gilt insgesamt:
[mm] $\left(\bruch{n}{2}\right)^{\bruch{n}{2}} \le [/mm] n! [mm] \le n^n$
[/mm]
Könnten wir also zeigen, daß [mm] $e^{\sqrt{n}} \le \left(\bruch{n}{2}\right)^{\bruch{n}{2}}$ [/mm] ist, so hätten wir auch deine Aussage bewiesen, also versuchen wir es mal:
[m]e^{\sqrt n } \leqslant \left( {\frac{n}
{2}} \right)^{\frac{n}
{2}} \Rightarrow \ln \left( {e^{\sqrt n } } \right) \leqslant \ln \left( {\left( {\frac{n}
{2}} \right)^{\frac{n}
{2}} } \right) \Rightarrow \sqrt n \leqslant \frac{n}
{2}\ln \left( {\frac{n}
{2}} \right) \Rightarrow 2 \leqslant \sqrt n \ln \left( {\frac{n}
{2}} \right)[/m]
Ich denke, damit wäre es gezeigt.
Grüße
Karl
|
|
|
|
![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
(vom Nachsatz natürlich mal abgesehen 
...)
