Potenz durch Fakultät < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:36 Mo 07.01.2013 | | Autor: | bandchef |
| Aufgabe | Zeigen oder widerlegen sie folgende Aussagen:
[mm] $2^n [/mm] = O(n!) = [mm] O(n^n)$ [/mm] |
Hi Leute!
In dieser Aufgabe geht's um Laufzeitkomplexität in Zuge einer Algorithmen Vorlesung.
Ich hab nun diesen Ansatz:
[mm] $\underbrace{2^n}_{=f(n)} [/mm] = O(n!) = [mm] \underbrace{O(n^n)}_{=g(n)}$
[/mm]
[mm] $\lim_{n \to \infty} \left( \left| \frac{g(n)}{f(n)} \right| \right) \leq [/mm] c$
[mm] $\lim_{n \to \infty} \left( \left| \frac{2^n}{n^n} \right| \right) [/mm] = ... = [mm] \lim_{n \to \infty} \left( \left| e^{n \cdot ln\left( \frac{2}{n}\right)} \right| \right) \leq [/mm] c$
An dieser Stelle weiß ich aber nicht mehr weiter. Bei solchen Betrachtungen gilt immer: $c [mm] \in \mathbb [/mm] R^+$. Was kommt beim limes raus? Der ln im Exponent geht nach [mm] $-\infty$ [/mm] das ranmultiplizierte n im Exponente geht nach [mm] $+\infty$...
[/mm]
Wie geht das?
|
|
| |
|
Hallo bandchef,
schau Dir mal den Exponenten separat an.
Was ist [mm] \lim_{n\to\infty}n*\ln{\left(\bruch{2}{n}\right)} [/mm] ?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:07 Mo 07.01.2013 | | Autor: | bandchef |
Also dann zerleg ich das mal:
Das "n" strebt nach plus unendlich. Das [mm] ln(\frac{2}{n}) [/mm] strebt nach minus unendlich. Also hab ich wohl [mm] $+\infty \cdot -\infty$ [/mm] und das geht ja nicht.
Wie löse ich das?
|
|
|
| |
|
Hallo nochmal,
> Also dann zerleg ich das mal:
>
> Das "n" strebt nach plus unendlich. Das [mm]ln(\frac{2}{n})[/mm]
> strebt nach minus unendlich. Also hab ich wohl [mm]+\infty \cdot -\infty[/mm]
> und das geht ja nicht.
Wieso geht das nicht? Das verstehe ich nicht.
Das Produkt strebt gegen [mm] -\infty.
[/mm]
> Wie löse ich das?
Das müsste doch jetzt gehen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:48 Di 08.01.2013 | | Autor: | bandchef |
Ja natürlich, du hast Recht. Das Produkt aus den beiden Unendlich geht gegen 0.
Somit hab ich nun $0 [mm] \leq [/mm] c$. Richtig?
|
|
|
| |
|
Hallo bandchef!
Ich unterstelle Dir mal, dass Du das Richtige zu meinen scheinst. Aber Du formulierst es sehr ... unglücklich.
> Ja natürlich, du hast Recht. Das Produkt aus den beiden
> Unendlich geht gegen 0.
Wenn Du hier [mm] $\limes_{n\rightarrow\infty}n*\ln\left(\bruch{2}{n}\right)$ [/mm] meinst, stimmt es nicht.
Es gilt: [mm] $n*\ln\left(\bruch{2}{n}\right) [/mm] \ [mm] \stackrel^{\longrightarrow}_{n\rightarrow\infty} [/mm] \ [mm] -\infty$ [/mm] .
Jedoch gilt: [mm] $\limes_{n\rightarrow\infty}e^{n*\ln\left(\bruch{2}{n}\right)} [/mm] \ = \ 0$ .
> Somit hab ich nun [mm]0 \leq c[/mm]. Richtig?
![[ok]](/images/smileys/ok.gif "[ok]")
Gruß vom
Roadrunner
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:59 Di 08.01.2013 | | Autor: | bandchef |
| Aufgabe | Nun hab ich noch diese Aufgabe gegeben:
[mm] $\lim_{n \to \infty}\left( \left| \frac{2^n}{n!} \right| \right) [/mm] = [mm] \lim_{n \to \infty}\left( \left| \frac{2^n}{\sqrt{2 \pi n\left( \frac{n}{e}\right)^n}} \right| \right) [/mm] = ...$ |
Das Problem ist nun die Grenzwertbetrachtung der Stirling-Formel im Nenner... Wie mach ich das hier jetzt? Mir geht Nenner als auch Zähler jeweils gegen plus Unendlich. Unendlich geteilt durch unendlich darf man ja nicht rechnen.
Das heißt ich müsste l'Hospital anwenden, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:04 Di 08.01.2013 | | Autor: | fred97 |
> Nun hab ich noch diese Aufgabe gegeben:
>
> [mm]\lim_{n \to \infty}\left( \left| \frac{2^n}{n!} \right| \right) = \lim_{n \to \infty}\left( \left| \frac{2^n}{\sqrt{2 \pi n\left( \frac{n}{e}\right)^n}} \right| \right) = ...[/mm]
>
> Das Problem ist nun die Grenzwertbetrachtung der
> Stirling-Formel im Nenner... Wie mach ich das hier jetzt?
> Mir geht Nenner als auch Zähler jeweils gegen plus
> Unendlich. Unendlich geteilt durch unendlich darf man ja
> nicht rechnen.
>
> Das heißt ich müsste l'Hospital anwenden, oder?
Weder noch.
Die reihe [mm] \summe_{n=0}^{\infty}\bruch{2^n}{n!} [/mm] konvergiert (gegen [mm] e^2). [/mm] Damit ist
[mm] (\bruch{2^n}{n!}) [/mm] eine Nullfolge.
FRED
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:10 Di 08.01.2013 | | Autor: | bandchef |
Dass diese Reihe gegen [mm] e^2 [/mm] konvergiert muss ja auch erst zeigen, oder? Wie zeigt man das?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:23 Di 08.01.2013 | | Autor: | fred97 |
> Dass diese Reihe gegen [mm]e^2[/mm] konvergiert muss ja auch erst
> zeigen, oder? Wie zeigt man das?
Du bist seit über 2 Jahren in diesem Forum in der Hochschulmathematik unterwegs.
Da sollte Dir bekannt sein, dass für jedes x [mm] \in \IR [/mm] die Reihe [mm] \summe_{n=0}^{\infty}\bruch{x^n}{n!} [/mm] konvergiert.
FRED
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 06:14 Di 08.01.2013 | | Autor: | fred97 |
Für n [mm] \ge [/mm] 3 ist
0 [mm] \le \bruch{2^n}{n^n} \le \bruch{2^n}{3^n}=(2/3)^n
[/mm]
FRED
|
|
|
|
