Wachstumshierarchie?

24.01.2008, 21:16

tevlon

Wachstumshierarchie?

Weiss jemand ,ob es eine art Wachstumshierarchie beschrieben wird ?

für ausreichend große n gilt doch :
$\begin{eqnarray*} 0< log n < n < n^2 < n^3 < x^n < n! < n^n \end{eqnarray*}$

ich kenn das ungefähr noch aus dem Matheunterricht ...würde das gerne nochmal nachlesen smile

24.01.2008, 22:12

brain man

Auf diesen Beitrag antworten »

Dabei helfen etwa die Landau-Symbole.

24.01.2008, 22:35

tevlon

Auf diesen Beitrag antworten »

Hi ,
Danke das bringt mich etwas weiter ...obwohl man die hierarchie nicht deutlich sehen kann...

Kann man das wissen auch bei der betrachtung des Limes verwenden ?

sprich : $\begin{eqnarray*} \lim_{n \to \infty } \frac{\log n}{n!} = 0 \end{eqnarray*}$ da n! schneller wächst ....

25.01.2008, 14:46

brain man

Auf diesen Beitrag antworten »

Das mag sicherlich in vielen Fällen zutreffen. Ein Gegenbsp. wäre aber :

$\begin{eqnarray*} \lim_{n \to \infty}\frac{n}{n+1}=1 \end{eqnarray*}$ ,obwohl der Nenner schneller als der Zähler wächst.

25.01.2008, 14:52

kiste

Auf diesen Beitrag antworten »

Die wachsen nach meiner Vorstellung gleich schnell(Die Ableitung ist ja auch gleich).

Der Vergleich mit dem limes ist gerade das kleine Landau-o

25.01.2008, 15:12

tevlon

Auf diesen Beitrag antworten »

Zitat:

Original von brain man
Das mag sicherlich in vielen Fällen zutreffen. Ein Gegenbsp. wäre aber :

Ok . das mit dem Gegenbeispiel stimmt ..
aber wenn wir vorraussetzen ,dass die höchste vorkommende Wachstumsklasse(?) nur im Zähler oder Nenner vorkommt ,dann müsste es stimmen.

wobei ich mir noch etwas unsicher bin :
$\begin{eqnarray*} n! < n^n \end{eqnarray*}$

da man n! auch mit der Stirlingschen Formel annähern kann unglücklich

25.01.2008, 15:37

Duedi

Auf diesen Beitrag antworten »

Behauptung: $\begin{eqnarray*} n^n > n! \end{eqnarray*}$
$\begin{eqnarray*} n^n = n\cdot n\cdot \cdots n\cdot \end{eqnarray*}$ (n Faktoren)
$\begin{eqnarray*} n! = n \cdot (n-1) \cdot \cdots \cdot 1 \end{eqnarray*}$ (n Faktoren)
$\begin{eqnarray*} \lim\limits_{n\to\infty}\frac{n!}{n^n}=\lim\limits_{n\to\infty}\frac{(n-1)!}{n^(n-1)} \end{eqnarray*}$ Achtung, im Nenner steht n^(n-1), LaTex stellt das nur ungenügend sichtbar dar.

$\begin{eqnarray*} =\lim\limits_{n\to\infty}\frac{n-1}{n}\cdot\frac{n-2}{n}\cdots\frac{1}{n} \end{eqnarray*}$

$\begin{eqnarray*} =1\cdot1\cdots\lim\limits_{n\to\infty}\frac{1}{n}=0 \end{eqnarray*}$

EDIT: Das Gegenbeispiel halte ich aus den selben Gründen wie kiste für unsinnig. Der Grenzwertvergleich dürfte in jedem Fall zutreffen

27.01.2008, 02:18

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Duedi
$\begin{eqnarray*} =\lim\limits_{n\to\infty}\frac{n-1}{n}\cdot\frac{n-2}{n}\cdots\frac{1}{n} \end{eqnarray*}$

$\begin{eqnarray*} =1\cdot1\cdots\lim\limits_{n\to\infty}\frac{1}{n}=0 \end{eqnarray*}$

Vorsicht hier, auseinanderziehen kannst du stets nur endlich viele Faktoren (deine Faktorenanzahl ist von n abhängig).

Schätze besser den Zähler geeignet nach oben ab, zB für gerade n: $\begin{eqnarray*} n! \le n^{\frac n 2} \cdot (\frac n 2)^{\frac n 2} \end{eqnarray*}$ .

Grüße Abakus smile

PS: a^{b + c} liefert dir in Latex b + c als Exponenten

Neue Frage »

Antworten »

Wachstumshierarchie?

Verwandte Themen